TO BE OR NOT TO BE
查看原帖
TO BE OR NOT TO BE
114226
哦great楼主2019/7/18 20:00

扒下数据本地提交A了前三个点,但是评测却WA了

代码

#include<bits/stdc++.h>
#define reg register
#define ll long long
using namespace std;
const ll M=998244353;
ll m,n,ans=0,sum=0,p,f[1005][1005],q,b[1001],c[1005],t,type,x,g[101][101][101];

inline ll read() {
	 ll s = 0, t = 0;  char ch = getchar();
	while(ch > '9' || ch < '0') t |= ch == '-', ch = getchar();
	while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return t ? -s : s;
}
ll ksm(ll u,ll v)
{
	ll s=1;
	for(ll i=v;i;i>>=1)
	{
		if(i&1)s=1LL*s*u%M;
		u=1LL*u*u%M;
	}
	return s;
}
void whh(ll u,ll v,ll hh,ll s)
{
	ll w=v;
	if(v>hh){v-=hh;hh=n-hh;}
	if(v>u)return ;
	p=n-u+1;
	q=p-(hh-v+1);
	//w=hh-v+1;
	sum=1;
	t=n;
	sum=1LL*sum*c[t-p]%M*c[hh]%M*c[n-hh]%M;
	sum=1LL*sum*ksm(c[t],M-2)%M*ksm(c[v-1],M-2)%M*ksm(c[n-hh-q],M-2)%M;

	sum=1LL*sum*c[p-1]%M*ksm(c[q],M-2)%M*ksm(c[p-q-1],M-2)%M;

	for(int r=1;r<=n;r++)
	{
		g[s][u][r]=(g[s][u][r]+g[s-1][w][r]*sum)%M;
	}

}
int main()
{
	n=read();
	
	m=read();
	type=read();
	c[0]=1;
	for(int i=1;i<=n*2;i++)c[i]=c[i-1]*i*1LL%M;
	for(int i=1;i<=m;i++)b[i]=read();
	for(int i=1;i<=n;i++)g[0][i][i]=1;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
			{
				whh(j,k,b[i],i);
			}

	q=read();
	while(q--)
	{
		x=read();
		ans=0;
		if(type==2)for(int i=1;i<=n;i++)ans=(ans+1ll*g[m][x][i]*i%M*i)%M;
		else for(int i=1;i<=n;i++)ans=(ans+1ll*g[m][x][i]*i%M)%M;

		printf("%lld\n",ans);
	}	


	return 0;
}



2019/7/18 20:00
加载中...