[cf1528F]AmShZ Farm

考虑$a_{i}$是"more-equal"的组合意义，有以下构造——

有$n$个位置，每一次选择一个位置$a_{i}$，在$a_{i}$之后（包括$a_{i}$）的第一个空位上停一辆车，那么$a_{i}$即要求每一辆车都可以停（不存在停到第$n+1$个位置及以后的情况）

关于这个问题，可以在之后新增一个位置，并将整个序列变成一个环，那么方案合法当且仅当第$n+1$个位置没有车，由于每一个位置没车的概率相同，即有$(n+1)^{n-1}$种方案

接下来，即对于每一组方案，令$tot_{i}=\sum_{1\le j\le n}[a_{j}=i]$，那么贡献即$\sum_{i=1}^{n}tot_{i}^{k}$

考虑枚举$i$和$tot_{i}$，那么即要求其中恰好$tot_{i}$次为$i$且第$n+1$个位置为空的方案数

由于$i$是任意的，可以看作对于所有$i$每一个位置没车的概率相同，也即有$\sum_{i=1}^{n}{n\choose i}i^{k}n^{n-i}$种方案

将$i^{k}$用第二类斯特林数来计算，即$\sum_{i=1}^{n}{n\choose i}n^{n-i}\sum_{j=0}^{i}{i\choose j}j!S(k,j)$（其中$S(n,m)$为第二类斯特林数）

将组合数展开并交换枚举顺序，即$\sum_{j=0}^{k}S(k,j)\sum_{i=1}^{n}\frac{n!n^{n-i}}{(i-j)!(n-i)!}$（显然当$n<m$时$S(n,m)=0$）

令$i'=i-j$并构造最后一项为二项式展开，即$\sum_{j=0}^{k}\frac{n!}{(n-j)!}S(k,j)\sum_{i'=0}^{n-j}{n-j\choose i'}n^{n-j-i'}$

根据二项式展开，即$\sum_{j=0}^{k}\frac{n!}{(n-j)!}(n+1)^{n-j}S(k,j)$

根据通项公式，即$S(n,m)=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{i}{m\choose i}(m-i)^{n}=\sum_{i=0}^{m}\frac{(-1)^{i}}{i!}\frac{(m-i)^{n}}{(m-i)!}$，直接ntt即可

时间复杂度为$o(k\log k)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N (1<<18)

 4 #define M 100005

 5 #define mod 998244353

 6 int n,k,ans,rev[N],a[N],b[N],fac[M],inv[M];

 7 int qpow(int n,int m){

 8     int s=n,ans=1;

 9     while (m){

10         if (m&1)ans=1LL*ans*s%mod;

11         s=1LL*s*s%mod;

12         m>>=1;

13     }

14     return ans;

15 }

16 void ntt(int *a,int p){

17     for(int i=0;i<N;i++)

18         if (i<rev[i])swap(a[i],a[rev[i]]);

19     for(int i=2;i<=N;i<<=1){

20         int s=qpow(3,(mod-1)/i);

21         if (p)s=qpow(s,mod-2);

22         for(int j=0;j<N;j+=i)

23             for(int k=0,ss=1;k<(i>>1);k++,ss=1LL*ss*s%mod){

24                 int x=a[j+k],y=1LL*ss*a[j+k+(i>>1)]%mod;

25                 a[j+k]=(x+y)%mod;

26                 a[j+k+(i>>1)]=(x-y+mod)%mod;

27             }

28     }

29     if (p){

30         int s=qpow(N,mod-2);

31         for(int i=0;i<N;i++)a[i]=1LL*a[i]*s%mod;

32     }

33 }

34 int main(){

35     scanf("%d%d",&n,&k);

36     fac[0]=inv[0]=inv[1]=1;

37     for(int i=1;i<M;i++)fac[i]=1LL*fac[i-1]*i%mod;

38     for(int i=2;i<M;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;

39     for(int i=1;i<M;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod;

40     for(int i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)+((i&1)<<17);

41     for(int i=0;i<=k;i++){

42         a[i]=inv[i];

43         if (i&1)a[i]=mod-a[i];

44     }

45     for(int i=0;i<=k;i++)b[i]=1LL*qpow(i,k)*inv[i]%mod;

46     ntt(a,0);

47     ntt(b,0);

48     for(int i=0;i<N;i++)a[i]=1LL*a[i]*b[i]%mod;

49     ntt(a,1);

50     int s=1;

51     for(int i=0;i<=min(n,k);i++){

52         ans=(ans+1LL*s*qpow(n+1,n-i)%mod*a[i])%mod;

53         s=1LL*s*(n-i)%mod;

54     }

55     printf("%d",ans);

56 }

巴特西

[cf1528F]AmShZ Farm

最新文章

热门文章