萌新刚学dp求助,没过样例
查看原帖
萌新刚学dp求助,没过样例
119062
Lates楼主2020/5/28 20:17

RT

代码是84分的部分分(正解AC了部分分写挂了qwq(

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int P= 998244353;
#define int long long 
inline int read(){
	register int x=0,f=0,ch=getchar();
	while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return f?-x:x;
}
const int MAX=45,MAXN=505; 
int f[MAXN][MAXN][MAXN],g[MAXN][MAXN];
// f[i][j][k] : 第 l 列,1-i 行在 l 列 j 个,其他列一共选 k 个 
// f[i][j][k] = f[i-1][j][k]+a[col][i]*f[i-1][j-1][k]+(s[i]-a[col][i])*f[i-1][j][k-1]
int s[MAX];// s[i]=\sum_{j=1}^{m}a[i][j]
int n,m,a[MAX][MAX],ans;
signed main(){
	n=read(),m=read();
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j){
			a[i][j]=read();
			s[i]=(s[i]+a[i][j])%P;
		}
	for(register int l=1;l<=m;++l){
		memset(f,0,sizeof(f));
		f[0][n][0]=1;
		for(register int i=1;i<=n;++i)
			for(register int j=1;j<=n;++j)
				for(register int k=1;k<=n;++k)
					f[i][j][k]=(f[i-1][j][k]+a[l][i]*f[i-1][j-1][k]%P+(s[i]-a[l][i])*f[i-1][j][k-1]%P)%P; 	
		for(register int j=1;j<n;++j)
			for(register int k=j+1;k<=n;++k)
				ans=(ans+f[n][j][k])%P;
	}
	g[0][0]=1;
	for(register int i=1;i<=n;++i){
		g[i][0]=g[i-1][0];
		for(register int j=1;j<=n;++j){
			g[i][j]=(g[i-1][j]+s[i]*g[i-1][j-1]%P)%P;
		}
	}
	ans=0;
	for(register int i=1;i<=n;++i){
		ans=(ans+g[n][i])%P;
	}
	ans=(ans+P)%P;
	printf("%lld\n",ans);
	return 0;
}


2020/5/28 20:17
加载中...