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)
[1leq 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}^inftyfrac{x^i}{i!})^n
]
这样的话可以做多项式快速幂
但是也可以换一个思路 利用(n,k)较小的性质
[(e^x-sum_{i=0}^{k-1}frac{x^i}{i!})^n = sum_{i=0}^n (-1)^n binom{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 << '
';
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);
}