icpc2019网络赛 上海站 e counting sequences ii [生成函数+泰勒展开]

Problem

构造一个长度为$n(n le 10^{18})$数列,每个数字属于$[1,m]$$(m le 2*10^5)$,要求每个偶数出现次数均为偶数次

Solution

多重集排列问题,用指数型生成函数处理

$G(x)=(1+frac{x^1}{1!}+frac{x^2}{2!}+frac{x^3}{3!}+dots)$

本题的指数型生成函数为

$G(x)=(1+frac{x^1}{1!}+frac{x^2}{2!}+frac{x^3}{3!}+dots)^{frac{m+1}{2}}(1+frac{x^2}{2!}+frac{x^4}{4!}+frac{x^6}{6!}+dots)^{frac{m}{2}}$

根据泰勒公式

$e^x=(1+frac{x^1}{1!}+frac{x^2}{2}+frac{x^3}{3!}+dots)$

$e^{-x}=(1-frac{x^1}{1!}+frac{x^2}{2!}-frac{x^3}{3!}+dots)$

得$G(x)=(e^x)^{frac{m+1}{2}}(frac{e^x+e^
{-x}}{2})^{frac{m}{2}}$

二项式展开后代入得第$n$项系数为$sum_{i=0}^{frac{m}{2}}C(frac{m}{2}, i)*(m-2ast i)^n$

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

using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
const int U = 200000;
int f[U + 3], rf[U + 3];
ll (ll a, ll m) { return (a == 1 ? 1 : inv(m % a, m) * (m - m / a) % m); }
void init() {
f[0] = 1;
for (int i = 1; i <= U; i++) f[i] = (ll)f[i - 1] * i % P;
rf[U] = inv(f[U], P);
for (int i = U; i; i--) rf[i - 1] = (ll)rf[i] * i % P;
}
ll C(int n, int m) {
if (m < 0 || m > n) return 0;
return (ll)f[n] * rf[m] % P * rf[n - m] % P;
}
ll powmod(ll a, ll b, ll P) {
ll t = 1;
for (; b; b >>= 1, a = a * a % P)
if (b & 1) t = t * a % P;
return t;
}
int T, m;
ll n;
int main() {
init();
scanf("%d", &T);
while (T--) {
scanf("%lld%d", &n, &m);
ll ans = 0;
int t = m >> 1;
for (int i = 0; i <= t; i++) {
ans = (ans + C(t, i) * powmod(m - 2 * i, n, P) % P) % P;
}
ans = ans * powmod(powmod(2, t, P), P - 2, P) % P;
printf("%lldn", ans);
}
return 0;
}