（期望DP）[NOI2019]斗主地

本文主要是介绍（期望DP）[NOI2019]斗主地，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

~~蒟蒻同步赛选手~~

考试的时候手推式子推了半天，结果只写个个 $O(mn^{2})$ ，水了 $\ 30$

我们设 $f_{i,j}$ 是经过 $\ i$ 次洗牌第 $\ j$ 张牌的期望（从下往上）， $fa_{i,j},fb_{i,j}$ 是两堆牌经过 $\ i$ 次洗牌的 $\ j$ 张牌的期望，我们有：

设 $\ A,B$ 是两堆牌的高度。

$f_{i,j}=\sum_{k=1}^{j} \frac{\binom{j-1}{k-1}A^{\underline{k}}B^{\underline{j-k}}(fa_{i-1,k})+\binom{j-1}{k-1}B^{\underline{k}}A^{\underline{j-k}}(fb_{i-1,k})}{n^{\underline{j}}}$

为甚会得到这个式子呢？

我们有以下分析：

先看这个图：

$\ c$ 的高度为 $\ A$ ， $\ d$ 的高度为 $\ B$

我们逐个分析：

先不考虑其顺序。

第一张牌：

如果我们取 $\ c1$ ，显然 $\ c1$ 的贡献为 $\ \frac{A}{n}c1$
如果我们取 $\ d1$ ，显然 $\ d1$ 的贡献为 $\ \frac{B}{n}d1$

第二张牌

如果我们取 $\ c1$ ，贡献为 $\ \frac{AB}{n(n-1)}c1$
如果我们取 $\ d1$ ，贡献为 $\ \frac{AB}{n(n-1)}d1$
如果我们取 $\ c2$ ，贡献为 $\ \frac{A(A-1)}{n(n-1)}c2$
如果我们取 $\ d2$ ，贡献为 $\ \frac{B(B-1)}{n(n-1)}d2$

$\cdots$

显然的，当我们第 $\ j$ 张选了 $\ ck$ 时，分子上肯定有 $\ n^{\underline{num}}$ ，分子上肯定有 $\ A^{\underline{k}}$ 和 $\ B^{\underline{j-k}}$ 。对于 $\ dk$ ，我们有同样的分析。

那么考虑顺序的话是很么呢？显然是一个组合数 $\ \binom{j-1}{k-1}$ 。这个请读者自己分析。

致辞我们可以得到代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const long long mod=998244353;
//char buf[1<<20],*fs,*ft;
//inline char getc()
//{return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))? 0 : *fs++;}
inline long long read()
{long long s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;}
//char buf1[1<<21],a1[20];int p11,p12=-1;
//inline void flush()
//{fwrite (buf1,1,p12+1,stdout),p12=-1;}
//inline void print(int x)
//{if(p12>1<<20) flush();if(x<0) buf1[++p12]=45,x=-x;
//do{a1[++p11]=x%10+48;}while(x/=10);
//do{buf1[++p12]=a1[p11];}while(--p11);buf1[++p12]='\n';}
/*
g the two line
f the c
frac n!
invf the inv of frac
a A
*/
long long n,m,a[100100],f[2][100100],frac[100100],invf[100100],g[1100][1100],type;
long long fa[100100],fb[100100];
inline long long poww(long long a,long long b)
{long long res=1ll;a%=mod;while(b){if(b&1){res*=a;res%=mod;}a*=a;a%=mod;b>>=1;}return res;
}
inline long long sum(int aa,int bb,int num,int k)
{long long ans=invf[n]*frac[n-num-1];ans%=mod;ans*=g[k-1][num-(k-1)];ans%=mod;int aused1,bused1,aused2,bused2;//ues in aaused1=k-1ll;bused1=num-(k-1ll);//use in baused2=num-(k-1ll);bused2=k-1ll;long long suma=frac[aa]*invf[aa-aused1];suma%=mod;if((aused1<aa)&&(bused1<=bb)){suma*=frac[bb];suma%=mod;suma*=invf[bb-bused1];suma%=mod;suma*=aa-aused1;suma%=mod;suma*=fa[k];suma%=mod;}else suma=0;long long sumb=frac[bb]*invf[bb-bused2];sumb%=mod;if((bused2<bb)&&(aused2<=aa)){sumb*=frac[aa];sumb%=mod;sumb*=invf[aa-aused2];sumb%=mod;sumb*=bb-bused2;sumb%=mod;sumb*=fb[k];sumb%=mod;}else sumb=0;long long sum=suma+sumb;sum%=mod;ans*=sum%mod;ans%=mod;return ans;
}
/*
have got num cards and the next is the kth
*/
signed main()
{
//	freopen("landlords.in","r",stdin);
//	freopen("landlords.out","w",stdout);memset(f,0,sizeof(f));memset(g,0,sizeof(g)); n=read();m=read();type=read();int i=1,j=1,k=1;while(i<=m){a[i]=read();++i;}g[0][0]=1;i=0;while(i<=n){j=0;while(j<=n){if(i) g[i][j]+=g[i-1][j];g[i][j]%=mod;if(j) g[i][j]+=g[i][j-1];g[i][j]%=mod;++j;}++i;}frac[0]=1;i=1;while(i<=n){frac[i]=frac[i-1]*i;frac[i]%=mod;++i;}i=0;while(i<=n){invf[i]=poww(frac[i],mod-2);invf[i]%=mod;++i;}i=1;while(i<=n){f[0][n-i+1]=poww(i,type);f[0][n-i+1]%=mod;++i;}int cur=0;i=1;while(i<=m){cur^=1;int aa=0,bb=0;j=n-a[i]+1;memset(f[cur],0,sizeof(f[cur]));memset(fa,0,sizeof(fa));memset(fb,0,sizeof(fb));while(j<=n){fa[++aa]=f[cur^1][j];++j;}j=1;while(j<=n-a[i]){fb[++bb]=f[cur^1][j];++j;}j=1;while(j<=n){k=1;while(k<=min(j,max(aa,bb))){f[cur][j]+=sum(aa,bb,j-1,k);f[cur][j]%=mod;++k;}++j;}++i;}int qq=read();while(qq--){int cc=read();
//		while(f[cur][n-cc+1]<0) f[cur][n-cc+1]+=mod;printf("%lld\n",f[cur][n-cc+1]);}return 0;
}

当然只有三十分， $O(mn^{2})$ 的复杂度是很不优秀的。

我们经过打表证明发现在 $\ f(i)=i$ 时答案是一个等差数列，那么我们就只需要记录前两项了。

证明：

我们思考一下这个过程：我们发现任意时刻我们的牌堆都是上面的牌没有下面的牌大的（不取膜）。我们挖掘这个东西的性质，发现它实际上是基数排序的逆过程。而且原序列的所有情况概率是相同的。

同理可得 $f(i)=i^{2}$ 的时候是二次函数

实际上我们不需要分情况讨论，一次函数本身就是特殊的二次函数。

此处我用拉格朗日插值就二次函数通项，大佬可以用二阶差分啥的。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const long long mod=998244353;
//char buf[1<<20],*fs,*ft;
//inline char getc()
//{return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))? 0 : *fs++;}
inline long long read()
{long long s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;}
//char buf1[1<<21],a1[20];int p11,p12=-1;
//inline void flush()
//{fwrite (buf1,1,p12+1,stdout),p12=-1;}
//inline void print(int x)
//{if(p12>1<<20) flush();if(x<0) buf1[++p12]=45,x=-x;
//do{a1[++p11]=x%10+48;}while(x/=10);
//do{buf1[++p12]=a1[p11];}while(--p11);buf1[++p12]='\n';}
/*
g the two line
f the c
frac n!
invf the inv of frac
a A
*/
long long n,m,a[500500],f[2][5],frac[10001000],invf[10001000],type;
long long fa[5],fb[5];
long long g(long long i,long long j)
{long long ans=frac[i+j];ans*=invf[i];ans%=mod;ans*=invf[j];ans%=mod;return ans;
}
inline long long poww(long long a,long long b)
{long long res=1ll;a%=mod;while(b){if(b&1){res*=a;res%=mod;}a*=a;a%=mod;b>>=1;}return res;
}
inline long long sum(int aa,int bb,int num,int k)
{long long ans=invf[n]*frac[n-num-1];ans%=mod;ans*=g(k-1,num-(k-1));ans%=mod;int aused1,bused1,aused2,bused2;//ues in aaused1=k-1ll;bused1=num-(k-1ll);//use in baused2=num-(k-1ll);bused2=k-1ll;long long suma=frac[aa]*invf[aa-aused1];suma%=mod;if((aused1<aa)&&(bused1<=bb)){suma*=frac[bb];suma%=mod;suma*=invf[bb-bused1];suma%=mod;suma*=aa-aused1;suma%=mod;suma*=fa[k];suma%=mod;}else suma=0;long long sumb=frac[bb]*invf[bb-bused2];sumb%=mod;if((bused2<bb)&&(aused2<=aa)){sumb*=frac[aa];sumb%=mod;sumb*=invf[aa-aused2];sumb%=mod;sumb*=bb-bused2;sumb%=mod;sumb*=fb[k];sumb%=mod;}else sumb=0;long long sum=suma+sumb;sum%=mod;ans*=sum%mod;ans%=mod;return ans;
}
/*
have got num cards and the next is the kth
*/
inline void getabc(long long x0,long long y0,long long x1,long long y1,long long x2,long long y2,long long &aa,long long &bb,long long &cc)
{aa=0;bb=0;cc=0;long long sum=0;//0a 0bsum=(x0-x1)*(x0-x2);sum%=mod;sum=poww(sum,mod-2);sum*=y0;sum%=mod;aa+=sum;aa%=mod;sum*=(x1+x2);sum%=mod;bb+=sum;bb%=mod;//1a 1bsum=(x1-x0)*(x1-x2);sum%=mod;sum=poww(sum,mod-2);sum*=y1;sum%=mod;aa+=sum;aa%=mod;sum*=(x0+x2);sum%=mod;bb+=sum;bb%=mod;//2a 2bsum=(x2-x0)*(x2-x1);sum%=mod;sum=poww(sum,mod-2);sum*=y2;sum%=mod;aa+=sum;aa%=mod;sum*=(x0+x1);sum%=mod;bb+=sum;bb%=mod;bb*=-1;bb%=mod;if(bb<0) bb+=mod;//0csum=(x0-x1)*(x0-x2);sum%=mod;sum=poww(sum,mod-2);sum*=y0;sum%=mod;sum*=x1;sum%=mod;sum*=x2;sum%=mod;cc+=sum;cc%=mod;//1csum=(x1-x0)*(x1-x2);sum%=mod;sum=poww(sum,mod-2);sum*=y1;sum%=mod;sum*=x0;sum%=mod;sum*=x2;sum%=mod;cc+=sum;cc%=mod;//2csum=(x2-x0)*(x2-x1);sum%=mod;sum=poww(sum,mod-2);sum*=y2;sum%=mod;sum*=x0;sum%=mod;sum*=x1;sum%=mod;cc+=sum;cc%=mod;
}
signed main()
{
//	freopen("landlords2.in","r",stdin);
//	freopen("landlords2.out","w",stdout);memset(f,0,sizeof(f)); n=read();m=read();type=read();int i=1,j=1,k=1;while(i<=m){a[i]=read();++i;}frac[0]=1;i=1;while(i<=n){frac[i]=frac[i-1]*i;frac[i]%=mod;++i;}invf[n]=poww(frac[n],mod-2);i=n;while(i>=1){invf[i-1]=invf[i]*i;invf[i-1]%=mod;--i;}i=n;while(i>=n-3){f[0][n-i+1]=poww(i,type);f[0][n-i+1]%=mod;--i;}int cur=0;i=1;while(i<=m){cur^=1;int aa=0,bb=0;memset(f[cur],0,sizeof(f[cur]));memset(fa,0,sizeof(fa));memset(fb,0,sizeof(fb));j=1;while(j<=3){fb[++bb]=f[cur^1][j];++j;}bb=n-a[i];aa=a[i];long long ax,bx,cx;getabc(1,fb[1],2,fb[2],3,fb[3],ax,bx,cx);int x=n-a[i]+1;j=1;while(j<=3){fa[j]=ax*x;fa[j]%=mod;fa[j]*=x;fa[j]%=mod;fa[j]+=(bx*x)%mod;fa[j]%=mod;fa[j]+=cx;fa[j]%=mod;++x;++j;}j=1;while(j<=3){k=1;while(k<=3){f[cur][j]+=sum(aa,bb,j-1,k);f[cur][j]%=mod;++k;}++j;}++i;}long long aaa,bbb,ccc;getabc(1,f[cur][1],2,f[cur][2],3,f[cur][3],aaa,bbb,ccc);int qq=read();while(qq--){int cc=read();cc=n-cc+1;int ans=0;ans=aaa*cc;ans%=mod;ans*=cc;ans%=mod;ans+=(cc*bbb)%mod;ans%=mod;ans+=ccc;ans%=mod;if(ans<0) ans+=mod;printf("%lld\n",ans);}return 0;
}