题目 设 p = 1 m p = \frac 1m p=m1 a n s = ∑ i = 0 k { k i } p i ( n i ) i ! = ∑ i = 0 k ∑ j = 0 i ( i j ) ( n i ) p i ( − 1 ) j ( i − j ) k = ∑ j = 0 k ( − 1 ) j ( n j ) ∑ i = j k ( n − j i − j ) p i ( i − j ) k = ∑ j = 0 k ( − 1 ) j p j ( n j ) ∑ i = 0 k − j ( n − j i ) p i i k = ∑ i = 0 k i k p i ∑ j = 0 k − i ( − p ) j ( n j ) ( n − j i ) = ∑ i = 0 k i k p i ( n i ) ∑ j = 0 k − i ( − p ) j ( n − i j ) \begin{aligned} ans &= \sum_{i=0}^k \begin{Bmatrix}k\\i\end{Bmatrix}p^i\binom nii! \\ &=\sum_{i=0}^k \sum_{j=0}^i \binom ij\binom nip^i(-1)^j(i-j)^k\\ &=\sum_{j=0}^k(-1)^j\binom nj \sum_{i=j}^k \binom{n-j}{i-j}p^i(i-j)^k\\ &=\sum_{j=0}^k(-1)^jp^j\binom nj\sum_{i=0}^{k-j} \binom {n-j}ip^ii^k\\ &=\sum_{i=0}^ki^kp^i\sum_{j=0}^{k-i} (-p)^j\binom nj\binom{n-j}i\\ &=\sum_{i=0}^ki^kp^i\binom ni\sum_{j=0}^{k-i}(-p)^j\binom{n-i}{j}\end{aligned} ans=i=0∑k{ki}pi(in)i!=i=0∑kj=0∑i(ji)(in)pi(−1)j(i−j)k=j=0∑k(−1)j(jn)i=j∑k(i−jn−j)pi(i−j)k=j=0∑k(−1)jpj(jn)i=0∑k−j(in−j)piik=i=0∑kikpij=0∑k−i(−p)j(jn)(in−j)=i=0∑kikpi(in)j=0∑k−i(−p)j(jn−i)
考虑 S i + 1 = ∑ j = 0 k − i − 1 ( − p ) j ( n − i − 1 j ) = ∑ j = 0 k − i − 1 ( − p ) j ( ( n − i j ) − ( n − i − 1 j − 1 ) ) = S i − ( − p ) k ( n − i k − i ) + p ( S i + 1 − ( − p ) k − i − 1 ( n − i − 1 k − i − 1 ) ) S_{i+1} = \sum_{j=0}^{k-i-1}(-p)^j\binom{n-i-1}j = \sum_{j=0}^{k-i-1}(-p)^j\left(\binom{n-i}j - \binom{n-i-1}{j-1}\right)\\=S_i-(-p)^k\binom {n-i}{k-i} + p\left(S_{i+1}-(-p)^{k-i-1}\binom {n-i-1}{k-i-1}\right) Si+1=j=0∑k−i−1(−p)j(jn−i−1)=j=0∑k−i−1(−p)j((jn−i)−(j−1n−i−1))=Si−(−p)k(k−in−i)+p(Si+1−(−p)k−i−1(k−i−1n−i−1))
可以得到 S i = S i + 1 ( 1 − p ) + ( − p ) k − i ( n − i − 1 k − i ) S_i = S_{i+1}(1-p) + (-p)^{k-i}\binom {n-i-1}{k-i} Si=Si+1(1−p)+(−p)k−i(k−in−i−1) 边界条件 S k = 1 S_k = 1 Sk=1。 所以 a n s = ∑ i = 0 k i k p i ( n i ) S i ans = \sum_{i=0}^k i^kp^i\binom ni S_i ans=i=0∑kikpi(in)Si O ( k ) O(k) O(k)线性筛预处理 i k i^k ik。 对于 ( n i ) \binom ni (in)需要求 n i ‾ n^{\underline i} ni 对于 ( n − i − 1 k − i ) \binom {n-i-1}{k-i} (k−in−i−1)需要求 ( n − k ) k − i ‾ (n-k)^{\overline {k-i}} (n−k)k−i 还有就是阶乘的逆元。 感觉可以搞搞模数搞拓展 l u c a s lucas lucas。
总复杂度 O ( k ) O(k) O(k) A C C o d e \mathcal AC \ Code AC Code
#include<bits/stdc++.h> #define maxn 10000007 #define rep(i,j,k) for(int i=(j),LIM=(k);i<=LIM;i++) #define per(i,j,k) for(int i=(j),LIM=(k);i>=LIM;i--) #define mod 998244353 using namespace std; int Pow(int b,int k){ int r=1;for(;k;k>>=1,b=1ll*b*b%mod) if(k&1)r=1ll*r*b%mod;return r; } int pr[maxn/8],cnt_pr,pwk[maxn],inv[maxn],s[maxn]; bool vis[maxn]; int n,m,K,p; int main(){ scanf("%d%d%d",&n,&m,&K);p = Pow(m , mod-2); pwk[1] = inv[0] = inv[1] = 1; rep(i,2,K){ inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; if(!vis[i]) pr[cnt_pr++] = i , pwk[i] = Pow(i,K); for(int j=0;pr[j] * i <= K;j++){ vis[i * pr[j]] = 1 , pwk[i * pr[j]] = 1ll * pwk[i] * pwk[pr[j]] % mod; if(i % pr[j] == 0) break; } } int C = 1 , pw = 1; rep(i,0,K){ s[K-i] = (s[K-i+1] * (1ll - p) + 1ll * pw * C) % mod; pw = 1ll * pw * (-p) % mod; C = 1ll * C * (n-K+i) % mod * inv[i+1] % mod; } C = 1 , pw = 1; int ans = 0; rep(i,0,K){ ans = (ans + 1ll * pwk[i] * pw % mod * C % mod * s[i]) % mod; pw = 1ll * pw * p % mod; C = 1ll * C * (n-i) % mod * inv[i+1] % mod; } printf("%d\n",(ans+mod)%mod); }