哪个大佬帮我看看牛客周赛113E吗?改了很久还是有错

#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
typedef  long long ll;
typedef pair<int, int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 9, M = 2e5 + 9, mod = 1e9 + 7;
int dpa[305][305][500];
int dpb[305][305][500];
void solve() {
	int n;
	cin >> n;
	vector<int> a(n+1),b(n+1);
	for(int i=1;i<=n;i++){
		cin >> a[i];
		a[i]%=495;
	}
	for(int i=1;i<=n;i++){
		cin >> b[i];
		b[i]%=495;
	}
	for(int i=0;i<=n;i++) dpa[i][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k<495;k++){
				//dpa[i][j][k]
				int v=(k+a[i])%495;
				dpa[i][j][v]=dpa[i-1][j][v];
				if(j-1>=0) dpa[i][j][v]=(dpa[i][j][v]+dpa[i-1][j-1][k])%mod;
			}
		}
	}
	for(int i=0;i<=n;i++) dpb[i][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k<495;k++){
				int v=(k+b[i])%495;
				dpb[i][j][v]=dpb[i-1][j][v];
				if(j-1>=0) dpb[i][j][v]=(dpb[i][j][v]+dpb[i-1][j-1][k])%mod;
			}
		}
	}
	//pre[i][j]表示从b中选至多i个数,模495为j的方案数
	vector<vector<int>> pre(n+1,vector<int>(495));
	for(int j=0;j<495;j++) pre[0][j]=dpb[n][0][j];
	
	for(int j=0;j<495;j++){
		for(int i=1;i<=n;i++){
			pre[i][j]=(pre[i-1][j]+dpb[n][i][j])%mod;
		}
	}
	vector<int> ans(495,0);
	//枚举a选择的个数
	for(int i=0;i<=n;i++){
		//a贡献j
		for(int j=0;j<495;j++){
			if(dpa[n][i][j]==0) continue;
			for(int k=0;k<495;k++){
				if(pre[i][k]==0) continue;
				int v=(j+k)%495;
				ans[v]=(ans[v]+dpa[n][i][j]*pre[i][k]%mod)%mod;
			}
		}
	}
	for(int i=0;i<495;i++){
		cout << ans[i] << " \n"[i==494];
	}
}
/*

*/
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

全部评论
1、dp数组得开ll;2、开ll三维数组爆内存,得滚动数组或压缩到二维
点赞 回复 分享
发布于 10-14 16:57 新加坡

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务