G.Product EGF解决排列问题
题意
给定整数\(n,k,D\)
定义权值
\[\frac{D!}{\prod_{i=1}^n(a_i + k)!}
\]
求出满足如下条件下的所有权值的和
- 1.\(\forall i \in [1,n],a_i \geq 0\)
- 2.\(\sum_{i=1}^na_i = D\)
\[1\leq n \leq 50\0 \leq k \leq 50\0 \leq D \leq 10^8
\]
分析
看到分母为阶乘的形式的数数题，尝试联想到\(EGF\)
Taylor级数
\[e^x = 1 + \frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}...
\]
那么
\[\sum_{\sum a_i = D} \frac{1}{\prod_{i=1}^na_i!} = [x^D](e^x)^n
\]
考虑到\(a_i + k \geq 0\)
令\(b_i =a_i + k \geq k\) 也就是\(\leq k\)的\(x^i\)不应该被计入贡献
有
\[\sum_{\sum b_i = D + nk}\frac{1}{\prod_{i=1}^n b_i!} = [x^{D+nk}](e^x - \sum_{i=0}^{k-1}\frac{x^i}{i!})^n
\]
这个时候可以考虑做
\[(\sum_{i=k}^\infty\frac{x^i}{i!})^n
\]
这样的话可以做多项式快速幂
但是也可以换一个思路 利用\(n,k\)较小的性质
\[(e^x-\sum_{i=0}^{k-1}\frac{x^i}{i!})^n = \sum_{i=0}^n (-1)^n\tbinom{n}{i}(\sum_{i=0}^{k-1}\frac{x^i}{i!})^i(e^x)^{n-i}
\]
注意到可以预处理出\(\sum_{i=0}^{k-1}\frac{x^i}{i!}\)的幂次，次数最多会到\(nk\)级别
这样将二项式展开就可以做\(O(n^2k^2)\)的暴力卷积
代码
这类题做的不多 感觉实现有些细节需要仔细考虑
#include<bits/stdc++.h>
#define pii pair<ll,ll>
#define fi first
#define se second
using namespace std;
typedef long long ll;
inline int rd(){
int x;
scanf("%d",&x);
return x;
}
const int MOD = 998244353;
inline int mul(int a,int b){
int res = (ll)a * b % MOD;
if(res < 0) res += MOD;
return res;
}
inline void add(int &a,int b){
a += b;
if(a >= MOD) a -= MOD;
}
inline void sub(int &a,int b){
a -= b;
if(a < 0) a += MOD;
}
const int maxn = 55;
int fac[maxn],iv[maxn];
int C[maxn];
inline int ksm(int a,int b = MOD - 2,int m = MOD){
int ans = 1;
int base = a;
while(b){
if(b & 1) ans = (ll)ans * base % m;
base = (ll)base * base % m;
b >>= 1;
}
return ans;
}
map<pii,int> mp;
//a! / b!
inline int Ffac(int a,int b){
//cout << a << ‘ ‘ << b << ‘\n‘;
if(mp.count(make_pair(a,b))) return mp[make_pair(a,b)];
int ans = 1;
for(int i = b + 1;i <= a;i++)
ans = mul(ans,i);
for(int i = a + 1;i <= b;i++)
ans = mul(ans,ksm(i));
return mp[make_pair(a,b)] = ans;
}
int main(){
fac[0] = 1;
for(int i = 1;i < 55;i++)
fac[i] = mul(fac[i - 1],i);
iv[54] = ksm(fac[54]);
for(int i = 53;i >= 0;i--)
iv[i] = mul(iv[i + 1],i + 1);
C[0] = 1;
int n = rd();
int k = rd();
int D = rd();
for(int i = 0;i < n;i++)
C[i + 1] = mul(C[i],mul(n - i,ksm(i + 1)));
vector<vector<int>> pol(n + 1);
vector<int> t(k);
for(int i = 0;i < k;i++){
t[i] = iv[i];
}
pol[1] = t;
for(int i = 2;i <= n;i++){
pol[i].resize(k + pol[i - 1].size() - 1);
for(int j = 0;j < k;j++){
for(int h = 0;h < pol[i - 1].size();h++){
add(pol[i][h + j],(ll)pol[i - 1][h] * t[j] % MOD);
}
}
}
/*
if(k == 1){
printf("%d",mul(ksm(n,D + n * k),Ffac(D,D + n * k)));
return 0;
}*/
int ans = mul(ksm(n,D + n * k),Ffac(D,D + n * k));
for(int i = 1;i <= n;i++){
int res = 0;
for(int j = 0;j < pol[i].size();j++){
int Need = D + n * k - j;
if(Need < 0) break;
add(res,mul(pol[i][j],mul(ksm(n - i,Need),Ffac(D,Need))));
}
res = mul(res,C[i]);
if(i & 1) res = MOD - res;
add(ans,res);
}
printf("%d",ans);
}