题解

1 条题解

  • 0
    @ 2018-09-30 09:29:05

    将所有序列的数量,减去全部数值都是合数的序列数量,就是有至少一个质数的序列的数量。然后可以想到一个递推:f(i, j)代表序列长度为i,所有数字之和mod p的值是j的话,序列的数量。用矩阵乘法做这个递推就可以了。

    #include <cstdio>
    
    #define mul(a, b) (((long long)(a) * (long long)(b)) % 20170408)
    
    bool composite[20000005];
    int composite_mod[105];
    int all_mod[105];
    
    using namespace std;
    
    int n, m, p;
    
    int matrix[100][100];
    int fastpow[32][100][100];
    int current[32][100];
    
    int calc(int* modlist)
    {
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < p; j++) {
                matrix[i][j] = fastpow[0][i][j] = modlist[(((j - i) % p) + p) % p];
            }
        }
        for (int pwr = 1; pwr < 32; pwr++) {
            for (int i = 0; i < p; i++) {
                for (int j = 0; j < p; j++) {
                    fastpow[pwr][i][j] = 0;
                    for (int k = 0; k < p; k++) {
                        fastpow[pwr][i][j] += mul(fastpow[pwr-1][i][k], fastpow[pwr-1][k][j]);
                        if (fastpow[pwr][i][j] >= 20170408) {
                            fastpow[pwr][i][j] -= 20170408;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < p; j++) {
                current[i][j] = 0;
            }
        }
        current[0][0] = 1;
        int working = 1;
        for (int bit = 0; bit < 32; bit++) {
            if (n & (1 << bit)) {
                for (int i = 0; i < p; i++) {
                    for (int j = 0; j < p; j++) {
                        current[working][i] += mul(current[working-1][j], fastpow[bit][j][i]);
                        if (current[working][i] >= 20170408) {
                            current[working][i] -= 20170408;
                        }
                    }
                }
                working++;
            }
        }
        return current[working-1][0];
    }
    
    int main()
    {
        scanf("%d%d%d", &n, &m, &p);
        /* Technically, this is incorrect, but good enough for our purposes */
        composite[1] = true;
        
        for (int i = 2; i <= 5000; i++) {
            if (!composite[i])
                for (int j = i << 1; j <= 20000000; j += i) {
                    composite[j] = true;
            }
        }
        int curmod = 1 % p;
        for (int i = 1; i <= m; i++) {
            all_mod[curmod]++;
            if (composite[i]) {
                composite_mod[curmod]++;
            }
            curmod++;
            if (curmod == p) {
                curmod = 0;
            }
        }
        printf("%d", (((calc(all_mod)-calc(composite_mod))
                 % 20170408) + 20170408) % 20170408);
        return 0;
    }
    
    
    
  • 1

信息

ID
2015
难度
1
分类
(无)
标签
递交数
36
已通过
28
通过率
78%
被复制
2
上传者