88 pts 求助
查看原帖
88 pts 求助
104466
konnyaku_cstdio楼主2020/11/6 18:35

奇了怪了,调遍了一堆可能取mod的地方,结果最后三个点还是WA

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define int long long
using namespace std;
const ll mod=998244353;
const int MAXN = 4040;
ll n,m,aans,abbs,tmp,sum;
ll x[MAXN][MAXN],xn[MAXN][MAXN],dptmp[MAXN][MAXN];
ll verq[MAXN],sumh[MAXN];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&xn[i][j]);
		}
	}
	swap(n,m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			x[i][j]=xn[j][i];
			sum+=x[i][j];
			sumh[i]+=x[i][j];
			verq[j]+=x[i][j];
			verq[j]%=mod;
			sumh[i]%=mod;
			sum%=mod;
		}
	}
	aans=1ll;
	for(int i=1;i<=m;i++){
		verq[i]+=1;
		aans=aans*verq[i]%mod;
		verq[i]-=1;
	}
	for(int i=1;i<=n;i++){
//		memset(dptmp,0,sizeof(dptmp));t
		dptmp[0][m]=1ll;
		for(int j=1;j<=m;j++){
			for(ll k=-min(sum-sumh[i],m);k<=min(m,sumh[i]);k++){
				if(k+m>0){
					dptmp[j][k+m]=(dptmp[j-1][k-1+m]*x[i][j]%mod+dptmp[j-1][k+1+m]*(((verq[j]-x[i][j])%mod+mod)%mod)%mod+dptmp[j-1][k+m])%mod;
				}
				else{
					dptmp[j][k+m]=(dptmp[j-1][k+1+m]*(((verq[j]-x[i][j])%mod+mod)%mod)%mod+dptmp[j-1][k+m])%mod;
				}
				if(j==m&&(k>0)){
					abbs+=dptmp[j][k+m];
					abbs%=mod;
				}
				//printf("%lld %lld %lld || %lld %lld %lld --%lld %lld %lld\n",i,j,k,dptmp[j-1][k-1+m],dptmp[j-1][k+1+m],dptmp[j-1][k+m],x[i][j],verq[j],dptmp[j][k+m]);
			}
		}
		for(int k=0;k<=m;k++)
			for(int j=0;j<=2*m+2;j++){
			dptmp[k][j]=0;
		}
	}
	//printf("--%lld %lld\n",aans,abbs);
	printf("%lld\n",((aans-abbs-1)%mod+mod)%mod);
	return 0;
}
2020/11/6 18:35
加载中...