生成函数和一点基本的容斥.

Description

假如要构造一个长为$n$的序列, 且每个位置都是$[1,m]$中的某个整数, 要求最后序列中各数的和被$p$整除, 且至少有一个质数.

Solution

这题相对BZOJ3992考虑的东西更少些.

总和模一个数余$0$, 这是明显的循环卷积. 由于确定至少一个质数不太好求, 我们可以用所有情况减去一个质数都没有的情况. 于是有两个生成函数: 一个是一般的在对应模数次项的系数上贡献, 还有一个是强制素数次项的系数不贡献.

$n$比较大, 要跑快速幂???. 不是好模数, 但$p$足够小了, $p^2$卷积即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define mod 20170408

using namespace std;
typedef long long ll;

const int maxn = 105;
const int maxm = 2e+7 + 1;

int n, m, p;
struct Mul {
  ll a[maxn];
  Mul() {
    memset(a, 0, sizeof a);
  }
  ll& operator[](int x) {
    return a[x];
  }
  inline Mul operator*(Mul rhs) {
    Mul ret;
    for (int i = 0; i < p; ++i)
      for (int j = 0; j < p; ++j)
        ret[(i + j) % p] = (ret[(i + j) % p] + a[i] * rhs[j] % mod) % mod;
    return ret;
  }
}all, exc;

int npr[maxm], pr[maxm >> 1], cnt;
inline void euler() {
  npr[1] = 1;
  for (int i = 2; i <= m; ++i) {
    if (!npr[i]) pr[++cnt] = i;
    for (int j = 1; j <= cnt && i * pr[j] <= m; ++j) {
      npr[i * pr[j]] = 1;
      if (!(i % pr[j])) continue;
    }
  }
}

inline void quick_power(Mul &a, int index) {
  Mul b = a; index--;
  while (index) {
    if (index & 1) b = b * a;
    index >>= 1;
    a = a * a;
  }
  a = b;
}

int main() {
  scanf("%d%d%d", &n, &m, &p);
  euler();
  for (int i = 1; i <= m; ++i) {
    all[i % p]++;
    if (npr[i])  exc[i % p]++;
  }
  quick_power(all, n);
  quick_power(exc, n);
  ll ans = (all[0] - exc[0] + mod) % mod;
  printf("%lld\n", ans);
  return 0;
}