Luogu 3702 [SDOI2017]序列计数

BZOJ 4818

感觉不难。

首先转化一下题目，“至少有一个质数”$=$“全部方案”$ - $“一个质数也没有”。

注意到$m \leq 2e7$，$[1, m]$内的质数可以直接筛出来。

设$f_{i, j}$表示当前长度序列为$i$，当前和模$p$的值是$j$的方案数，直接无脑枚举$m$转移复杂度是$O(nmp)$的，但是发现每一次转移形式都是相同的。

$$f_{i, x} = \sum f_{i - 1, y}(y + z \equiv x(\mod p))$$

其实在模$p$的意义下大于等于$p$的数可以直接归类到这个数模$p$这一档里面，也就是说，我们可以记一个$cnt_x$表示模$p$意义下相同的数有$x$个。

$$f_{i, (x + y) \mod p} = \sum f_{i - 1, x} \times cnt_y$$

发现这个式子的形式很像矩阵快速幂的样子，然后就把转移写成矩阵的形式快速幂一下就好了。

转移矩阵的第$(i, j)$个格子是$\sum_{(i + k) \equiv j(\mod p)}cnt_k$

时间复杂度$O(m + p^3logn)$。

咕，感觉时间刚刚好。

然而再次观察一下这个式子发现是一个卷积的形式，因此可以直接$NTT$，时间复杂度可以降到$O(m + plogplogn)$，但是在这题中$p$太小了$ + $模数不好，直接暴力卷积的时间表现应该比$NTT$要优秀。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 2e7 + ;

const int M = ;

const ll P = 20170408LL;

int n, m, K, pCnt = , pri[N], cnt[M];

bool np[N];

template <typename T>

inline void inc(T &x, T y) {

    x += y;

    if (x >= P) x -= P;

}

template <typename T>

inline void sub(T &x, T y) {

    x -= y;

    if (x < ) x += P;

}

struct Matrix {

    int tn, tm;

    ll s[M][M];

    inline void init() {

        tn = tm = ;

        memset(s, , sizeof(s));

    }

    friend Matrix operator * (const Matrix x, const Matrix y) {

        Matrix res;

        res.init();

        res.tn = x.tn, res.tm = y.tm;

        for (int k = ; k < x.tm; k++)

            for (int i = ; i < x.tn; i++)

                for (int j = ; j < y.tm; j++)

                    inc(res.s[i][j], x.s[i][k] * y.s[k][j] % P);

        return res;

    }

    inline Matrix fpow(int y) {

        Matrix x = *this, res;

        res.init();

        res.tn = x.tn, res.tm = x.tm;

        for (int i = ; i < x.tn; i++) res.s[i][i] = ;

        for (; y ; y >>= ) {

            if (y & ) res = res * x;

            x = x * x;

        }

        return res;

    }

    inline void print() {

        for (int i = ; i < tn; i++)

            for (int j = ; j < tm; j++)

                printf("%lld%c", s[i][j], " \n"[j == tm - ]);

        printf("\n");

    }

} trans, ans;

inline void sieve() {

    np[] = ;

    for (int i = ; i <= m; i++) {

        if (!np[i]) pri[++pCnt] = i;

        for (int j = ; j <= pCnt && pri[j] * i <= m; j++) {

            np[i * pri[j]] = ;

            if (i % pri[j] == ) break;

        }

    }

}

inline ll solve1() {

    memset(cnt, , sizeof(cnt));

    for (int i = ; i <= m; i++) ++cnt[i % K];

    trans.init();

    trans.tn = trans.tm = K;

    for (int i = ; i < K; i++)

        for (int j = ; j < K; j++)

            inc(trans.s[i][(i + j) % K], 1LL * cnt[j]);

//    trans.print();

    trans = trans.fpow(n);

//    trans.print();

    ans.init();

    ans.s[][] = ;

    ans.tn = , ans.tm = K;

    ans = ans * trans;

    return ans.s[][];

}

inline ll solve2() {

    sieve();

    memset(cnt, , sizeof(cnt));

    for (int i = ; i <= m; i++)

        if (np[i]) ++cnt[i % K];

/*    for (int i = 0; i < K; i++)

        printf("%d%c", cnt[i], " \n"[i == K - 1]);    */

    trans.init();

    trans.tn = trans.tm = K;

    for (int i = ; i < K; i++)

        for (int j = ; j < K; j++)

            inc(trans.s[i][(i + j) % K], 1LL * cnt[j]);

//    trans.print();

    trans = trans.fpow(n);

//    trans.print();

    ans.init();

    ans.s[][] = ;

    ans.tn = , ans.tm = K;

    ans = ans * trans;

    return ans.s[][];

}

int main() {

    scanf("%d%d%d", &n, &m, &K);

//    printf("%lld\n", solve1());

//    printf("%lld\n", solve2());

    printf("%lld\n", (solve1() - solve2() + P) % P);

    return ;

}

巴特西

Luogu 3702 [SDOI2017]序列计数

最新文章

热门文章