原文链接 https://www.cnblogs.com/cly-none/p/UOJ450.html
题意:请自行阅读。
考虑用生成函数来表示答案。因为秒之间是有序的,所以这应当是个指数生成函数。故答案就是
[[x^n] left( sum_{i geq 0} frac {x^i} {i!} [d | i]
ight)^k
]
突破口显然是在([d|i])上。
于是考虑使用单位根反演。也就是
[frac {1} {n} sum_{i=0}^{n-1} omega_{n}^{ik} = [n | k]
]
于是就直接带入,得到
[egin{aligned}
sum_{i geq 0} frac {x^i} {i!} [d | i] = & sum_{i geq 0} frac {x^i} {i!} left (frac 1 d sum_{j=0}^{d-1} omega_{d}^{ij}
ight) \
= & frac 1 d sum_{j=0}^{d-1} sum_{i geq 0} frac {x^i omega_{d}^{ij}} {i!} \
= & frac 1 d sum_{j=0}^{d-1} e^{w_{d}^j x}
end{aligned}
]
本题中模数(MOD)为(19491001),满足(3 | (MOD -1))。
考虑这道题中(d leq 3),且我们很容易求出(e^{kx})中(x^n)前的系数。因此我们可以直接把这个式子展开为(d)项,再用二项式定理暴力计算答案。
复杂度是(O(k^{d-1})),能通过本题。(请注意所有四个子任务的分值之和为100)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
#define fir first
#define sec second
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define rrp(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define gc() getchar()
template <typename tp>
inline void read(tp& x) {
x = 0; char tmp; bool key = 0;
for (tmp = gc() ; !isdigit(tmp) ; tmp = gc())
key = (tmp == '-');
for ( ; isdigit(tmp) ; tmp = gc())
x = (x << 3) + (x << 1) + (tmp ^ '0');
if (key) x = -x;
}
const int N = 500010, MOD = 19491001, G = 7;
int jc[N], inv[N];
int power(int a,int b) {
int ret = 1;
while (b) {
if (b & 1) ret = 1ll * ret * a % MOD;
a = 1ll * a * a % MOD;
b >>= 1;
}
return ret;
}
int comb(int a,int b) {
if (a < b || a < 0 || b < 0) return 0;
return 1ll * jc[a] * inv[b] % MOD * inv[a-b] % MOD;
}
int n,k,d,ans;
int main() {
cin >> n >> k >> d;
jc[0] = 1;
rep (i, 1, k) jc[i] = 1ll * jc[i-1] * i % MOD;
inv[k] = power(jc[k], MOD - 2);
rrp (i, k-1, 0) inv[i] = 1ll * inv[i+1] * (i+1) % MOD;
if (d == 1) {
printf("%d
", power(k, n));
} else if (d == 2) {
for (int i = 0 ; i <= k ; ++ i)
(ans += 1ll * comb(k, i) * power(k - 2 * i, n) % MOD) %= MOD;
ans = 1ll * ans * power((MOD + 1) / 2, k) % MOD;
printf("%d
", ans);
} else if (d == 3) {
int va = power(G, (MOD - 1) / 3);
int vb = power(va, 2);
int vc = power(va, 3);
rep (a, 0, k) rep (b, 0, k-a) {
int c = k - a - b;
ans += 1ll * jc[k] * inv[a] % MOD * inv[b] % MOD * inv[c] % MOD * power((1ll * va * a + 1ll * vb * b + 1ll * vc * c) % MOD, n) % MOD;
ans %= MOD;
}
ans = 1ll * ans * power(power(3, MOD-2), k) % MOD;
printf("%d
", ans);
}
return 0;
}
小结:无。