# 1 条题解

• @ 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