Link to LOJ
Legend
給定 \(n,x,p,m,a_i\)，求：
\[\left(\sum\limits_{k=0}^{n}f(k)\times x^k \times \dbinom{n}{k} \right) \bmod p
\]
保證 \(1 \le n,x,p \le 10^9\)，\(0 \le a_i \le 10^9\)，\(0 \le m \le \min(1000 ,n)\)。
時空 \(\textrm{1s/512MB}\)
Editorial
作為 聯合省選2020 的第二題，居然還是一道良心送溫暖題，但至少區分掉了我，讓我們一起為出題人點贊。
just Stirling
\[\begin{aligned}
& \sum\limits_{k=0}^{n}f(k)\times x^k \times \dbinom{n}{k} \\
=& \sum_{k=0}^{n}\left(\sum_{i=0}^{m} a_ik^i\right) x^k\dbinom{n}{k} & 把多項式打開\\
=& \sum_{k=0}^{n}\left(\sum_{i=0}^{m} a_i\sum_{j=0}^{k}\begin{Bmatrix} i \\ j\end{Bmatrix}\dbinom{k}{j}j! \right) x^k\dbinom{n}{k} & 把 k^i 用第二類斯特林數打開\\
=& \sum_{k=0}^{n}\left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix}j! \right) x^k\dbinom{n}{k}\dbinom{k}{j} & 更改枚舉上界+移項\\
=& \left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix} \right) \sum_{k=0}^{n} x^k\dbinom{n}{j}\dbinom{n-j}{k-j} j! & 組合意義化簡\\
=& \left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix} \dbinom{n}{j}\right) \sum_{k=0}^{n} x^k\dbinom{n-j}{k-j} j! \\
=& \left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix} \dbinom{n}{j}\right) x^j\sum_{k=0}^{n-j} x^{k}\dbinom{n-j}{k} j! & 更改枚舉下标\\
=& \left(\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix} \right) x^j(x+1)^{n-j} n^{\underline j} & 二項式定理\\
=&\sum_{i=0}^{m} a_i\sum_{j=0}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix}x^j(x+1)^{n-j} n^{\underline j} \\
\end{aligned} \\
\]
以下是上文所需的三個式子：
\[\begin{aligned}
x^n &=\sum\limits_{i=0}^{x}\begin{Bmatrix} n\\ i\end{Bmatrix}\dbinom{x}{i}i! & 把 k^i 用第二類斯特林數打開 & (1)\\
\dbinom{n}{k}\dbinom{k}{m} &= \dbinom{n}{m}\dbinom{n-m}{k-m} & 組合意義化簡& (2)\\
(x+y)^n&=\sum\limits_{i=0}^{n}\dbinom{n}{i}x^i y^{n-i} & 二項式定理& (3)\\
\end{aligned}
\]
以及注意跟組合數學有關的式子有時候是可以更改枚舉上界的，這是因為斯特林數或組合數在這種情況下為 \(0\)。
然後你就發現第二類斯特林數 \(O(m^2)\) 求，沒了。
真的沒了嗎？
a mistake
發現對于 \((1)\) 式，\(n=0\) 時不成立，是以要單獨考慮 \(a_0\) 造成的貢獻為 \(a_0(x+1)^n\)。其餘的貢獻是 \(\sum\limits_{i=1}^{m} a_i\sum\limits_{j=1}^{m}\begin{Bmatrix} i \\ j\end{Bmatrix}x^j(x+1)^{n-j} n^{\underline j}\)。
Code
代碼不難。
// Author : Imakf
#include <bits/stdc++.h>
#define LL long long
LL n ,p ,m;
LL qpow(LL a ,LL b ,LL mod){
if(b < 0) return 0;
LL Ans = 1 % mod;
while(b){if(b & 1) Ans = Ans * a % mod;
a = a * a % mod ,b >>= 1;
}return Ans;
}
const int MX = 1000 + 233;
LL a[MX] ,xp1[MX] ,x[MX] ,S[MX][MX] ,nd[MX];
int main(){
std::cin >> n >> x[1] >> p >> m;
for(int i = 0 ; i <= m ; ++i) std::cin >> a[i];
x[0] = 1;
S[1][1] = 1;
nd[0] = 1;
for(int i = 2 ; i <= m ; ++i){ // ball
for(int j = 1 ; j <= i ; ++j){ // box
S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * j) % p;
// printf("S[%d][%d] = %lld\n" ,i ,j ,S[i][j]);
}
x[i] = x[i - 1] * x[1] % p;
}
for(int i = 0 ; i <= m ; ++i) xp1[i] = qpow(x[1] + 1 ,n - i,p);
for(int i = 1 ; i <= m ; ++i) nd[i] = nd[i - 1] * (n - i + 1) % p;
LL Ans = a[0] * xp1[0] % p;
for(int i = 1 ; i <= m ; ++i){
for(int j = 1 ; j <= i ; ++j){
Ans = (Ans + a[i] * S[i][j] % p * x[j] % p * xp1[j] % p * nd[j]) % p;
// printf("%lld\n" ,Ans);
}
}
std::cout << Ans << std::endl;
return 0;
}