ACM模版

描述

题解

看到讨论区曹鹏大牛的详细题解，我已经写不出什么拿得出✋的题解了，差距太大，毕竟我还只是一个渣渣~~~

努力了一下午，企图实现大牛的思路，可是有的地方难度比较大，理解起来很费力，所以只实现了部分思路，但是对付V1足够了，毕竟曹鹏大牛的思路是可以搞掉V2和V3的……Orz！！！

看来要好好研究一下大牛们的代码了，看看究竟怎么实现了这么复杂的思路。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
const int MAXM = 30;

ll g[MAXM];
ll f[2][MAXN];
ll cnt = 1;
ll res[MAXM] = {
  1};

struct mat
{
    ll A[21][21];
    mat operator * (const mat &a) const
    {
        mat b;
        for (int i = 0; i < cnt; i++)
        {
            for (int j = 0; j < cnt; j++)
            {
                b.A[i][j] = 0;
                for (int k = 0; k < cnt; k++)
                {
                    b.A[i][j] += A[i][k] * a.A[k][j] % MOD;
                    b.A[i][j] %= MOD;
                }
            }
        }
        return b;
    }
    mat operator + (const mat &a) const
    {
        mat b;
        for (int i = 0; i < cnt; i++)
        {
            for (int j = 0; j < cnt; j++)
            {
                b.A[i][j] = (A[i][j] + a.A[i][j]) % MOD;
            }
        }
        return b;
    }
};

ll slove(ll n)
{
    if (n < cnt)
    {
        return res[n];
    }
    n = n - cnt + 1;
    mat p, R;
    memset(p.A, 0, sizeof(p.A));
    memset(R.A, 0, sizeof(R.A));
    for (int i = 0; i < cnt; i++)
    {
        p.A[i][i] = 1;
    }
    for (int i = 0; i < cnt; i++)
    {
        R.A[cnt - 1][i] = g[cnt - i];
    }
    for (int i = 1; i < cnt; i++)
    {
        R.A[i - 1][i] = 1;
    }
    for (ll i = 0; i < 31; i++)
    {
        if ((1ll << i) & n)
        {
            p = p * R;
        }
        R = R * R;
    }
    ll g = 0;
    for (int i = 0; i < cnt; i++)
    {
        g += p.A[cnt - 1][i] * res[i] % MOD;
        g %= MOD;
    }
    return g;
}

int main()
{
    ll N, M;
    scanf("%lld%lld", &N, &M);

    while ((1LL << cnt) <= N)
    {
        cnt++;
    }

    bool flag = true;
    for (ll i = N / 2 + 1, j = 1; i <= N; i++, j++)
    {
        f[0][i] = j;
    }
    for (ll i = 0; i < cnt; i++, flag = !flag)
    {
        g[i + 1] = f[!flag][N];
        for (int j = 1; j <= N; j++)
        {
            ll a = (2 * j <= N) ? (f[!flag][N] - f[!flag][j * 2 - 1] + MOD) % MOD : 0;
            f[flag][j] = f[flag][j - 1] + a;
            f[flag][j] %= MOD;
        }
    }
    for (ll i = 1; i < cnt; i++)
    {
        for (ll j = 0; j < i; j++)
        {
            res[i] += res[j] * g[i - j] % MOD;
            res[i] %= MOD;
        }
    }
    printf("%lld\n", slove(M));

    return 0;
}