我错了。

只是一个式子：$[k\ |\ n]=\frac{1}{k}\sum_{i=0}^{k-1}(\omega_k^i)^n$。

LOJ6247

$\sum_{i \geqslant 0} [k \ | \ i] \big ( {n \atop i} \big) = \sum_{i \geqslant 0} \frac{1}{k}\sum_{j=0}^{k-1} (\omega_k^j)^i \big ( {n \atop i} \big) = \frac{1}{k} \sum_{j=0}^{k-1} \sum_{i \geqslant 0}(\omega_k^j)^i \big ( {n \atop i} \big ) = \frac{1}{k} = \sum_{j=0}^{k-1} (\omega_k^j + 1) ^ 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
int k, ans, wn;
ll n;

inline int add(int x, int y) {
	x += y; return x < mod ? x : x - mod;
}
inline int mul(int x, int y) {
	return 1ll * x * y % mod;
}
inline int fpow(int x, ll y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

int main() {
	scanf("%lld%d", &n, &k);
	wn = fpow(3, (mod - 1) / k);
	for (int i = 0, w = 1; i < k; ++i, w = mul(w, wn)) 
		ans = add(ans, fpow(add(w, 1), n));
	printf("%d", mul(ans, fpow(k, mod - 2)));
}

[集训队作业2018]复读机

一个复读机的生成函数为：$\sum_{i \geqslant 0} [d \ | \ i]\frac{x^i}{i!}=\sum_{i \geqslant 0} \frac{1}{d} \sum_{j=0}^{d-1} (\omega_d^j)^i \frac{x^i}{i!}= \frac{1}{d} \sum_{j=0}^{d-1}e^{\omega_d^jx}$。

我们要求这个生成函数的$k$次的$x^n$项系数。枚举对于每个$j$，$e^{\omega_d^jx}$被选了几次。注意到确定了前$d-1$项之后，最后一项被选了几次直接确定了。复杂度为$O(k^{d-1}\log 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
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000, mod = 19491001;
int n, inv[maxn + 10], fac[maxn + 10], ifac[maxn + 10];
int k, d, ans;

inline int add(int x, int y) {
	x += y; return x < mod ? x : x - mod;
}
inline int dec(int x, int y) {
	x -= y; return x < 0 ? x + mod : x;
}	
inline int mul(int x, int y) {
	return 1ll * x * y % mod;
}
inline int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

void prework() {
	fac[0] = ifac[0] = 1;
	for (int i = 1; i <= maxn; ++i) {
		fac[i] = mul(fac[i - 1], i);
		inv[i] = i == 1 ? 1 : dec(0, mul(mod / i, inv[mod % i]));
		ifac[i] = mul(ifac[i - 1], inv[i]);
	}
}
inline int comb(int x, int y) {
	return mul(fac[x], mul(ifac[y], ifac[x - y]));
}

int main() {
	prework();
	scanf("%d%d%d", &n, &k, &d);
	if (d == 1) printf("%d", fpow(k, n));
	else if (d == 2) {
		int wn = fpow(7, (mod - 1) / 2);
		for (int i = 0; i <= k; ++i)
			ans = add(ans, mul(comb(k, i), fpow(add(i, mul(wn, k - i)), n)));
		printf("%d", mul(ans, fpow(fpow(d, k), mod - 2)));
	} else {
		int wn = fpow(7, (mod - 1) / 3);
		for (int i = 0; i <= k; ++i)
			for (int j = 0; i + j <= k; ++j)
				ans = add(ans, mul(comb(k, i), mul(comb(k - i, j), fpow(add(i, add(mul(wn, j), mul(mul(wn, wn), k - i - j))), n))));
		printf("%d", mul(ans, fpow(fpow(d, k), mod - 2)));
	}
}