初見安~這裡是傳送門:Codeforces Educational Codeforces Round 78 F Cards
Sol
題意:m張牌,有一張是小醜,随機洗牌n次看最上面的一張牌,求這一張是小醜的期望次數的k次方。
這個k次方一加,這個題就十分靈性了。
首先我們先按題意寫出式子:每一次看到小醜的機率是
,我們就可以枚舉期望次數:
但是n的範圍明顯我們連
都不能寫。并且我們可以發現k的範圍很小。看到後面的i^k以及第二類斯特林數展開式結合二項式反演的優秀性質【即替換i^k後大多可以把複雜度的上限落到k上】,我們決定用第二類斯特林數替換一下i^k,也就是:
【對這一步感到很迷惑的看官,可以到這裡看一看,兩題套路極其相似,該題也相對簡單一些】
第二類斯特林數我們可以把他的展開式卷積起來用NTT求,是以我們把j循環換到前面:
其實這裡j循環的上限應該是
,因為第二類斯特林數的定義下j一定小于等于k。是以現在我們要把後面的i循環給整掉。怎麼整?先讓它看起來好看一點:
現在,如果再把組合數給拆乘階乘,把與i無關的項提到i循環前面j循環後面去,是不是就可以湊一個n-j個卷積了?是的,但是!!!看到n的範圍你就知道了,這根本卷不起來,并且這個上限怎麼都降不下去。這就是這個題迷惑的地方,我們不能直接把後面的循環也NTT卷積。那我們再觀察吧。有個組合數,有兩項,兩項之和為1并且幂次之和距離n-j就多了一個j。哦!這不是可以二項式定理替換掉嘛!!!【反正我沒想到】
我們把1/m的j次方提到前面去,後面整個i循環就可以用二項式展開換掉了。
【二項式定理:
】
好!現在我們看起來就可以直接
做了!
是嗎?
我們再把式子展開:
看到那個n!了嗎?這沒辦法預處理咋辦?其實n!和(n-j)!可以一起寫成n的j下降幂,暴力從n-j+1乘到n就好了,因為j的範圍也是受k限制的。這樣複雜度就是
,能過。當然還有别的關于二項式的替換方法,本狸不會QuQ
上代碼——
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 20004
using namespace std;
typedef long long ll;
const int mod = 998244353, mx = 2e4;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
int n, m, k;
ll fac[maxn], inv[maxn];
ll pw(ll a, ll b) {ll res = 1; while(b) {if(b & 1) res = res * a % mod; a = a * a % mod, b >>= 1;} return res;}
int len = 1, l = 0, r[maxn];
void NTT(ll *c, int op) {
for(int i = 1; i <= len; i++) if(i < r[i]) swap(c[i], c[r[i]]);
for(int mid = 1; mid < len; mid <<= 1) {
ll gn = pw(3, (mod - 1) / (mid << 1));
if(op == -1) gn = pw(gn, mod - 2);
for(int ls = 0, L = mid << 1; ls < len; ls += L) {
ll g = 1;
for(int k = 0; k < mid; k++, g = g * gn % mod) {
ll x = c[ls + k], y = c[ls + mid + k] * g % mod;
c[ls + k] = (x + y) % mod, c[ls + k + mid] = (x - y + mod) % mod;
}
}
}
if(op == -1) {
ll rev = pw(len, mod - 2);
for(int i = 0; i <= len; i++) c[i] = c[i] * rev % mod;
}
}
ll F[maxn], G[maxn], ans = 0;
signed main() {
n = read(), m = read(), k = read();
fac[0] = inv[0] = 1;//為什麼要預處理?第二類斯特林數還是會用一下下的就順手寫了……
for(int i = 1; i <= mx; i++) fac[i] = fac[i - 1] * i % mod;
inv[mx] = pw(fac[mx], mod - 2);
for(int i = mx - 1; i > 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
for(int i = 0; i <= k; i++) F[i] = pw(i, k) * inv[i] % mod;
for(int i = 0, kd = 1; i <= k; i++, kd = -kd) G[i] = (kd * inv[i] % mod + mod) % mod;
while(len <= k + k) len <<= 1, l++;
for(int i = 0; i <= len; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << l - 1);
NTT(F, 1), NTT(G, 1);
for(int i = 0; i <= len; i++) F[i] = F[i] * G[i] % mod;
NTT(F, -1);//第二類斯特林數卷積完了
for(int i = 0; i <= k; i++) {
ll res = 1;
for(int j = n; j > n - i; j--) res = res * j % mod;//暴力n的j下降幂
ans = (ans + F[i] * res % mod * pw(pw(m, mod - 2), i) % mod) % mod;
}
printf("%lld\n", ans);
return 0;
}
迎評:)
——End——