消失之物——卷积做法
  • 板块P4141 消失之物
  • 楼主Zxsoul
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/5/8 14:47
  • 上次更新2023/11/4 23:33:22
查看原帖
消失之物——卷积做法
230808
Zxsoul楼主2021/5/8 14:47

我用卷积做个 8080 各位看看哪里出错了,后二三个点挂了

#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 1e7+10;
const int B = 1e6+10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

int v[B],f[3000][3000],g[3000][3000],n,m,w[B];
main()
{
	n=read(),m=read();
	for (int i=1;i<=n;i++)	w[i]=read();
	for (int i=1;i<=n;i++)	v[n-i+1]=w[i];
	
	f[0][0]=g[0][0]=1;
	for (int i=1;i<=n;i++)
		for (int j=0;j<=m;j++)
		{
			if (j<w[i])	f[i][j]+=f[i-1][j];
			else
			{
				f[i][j]+=f[i-1][j];
				f[i][j]+=f[i-1][j-w[i]];
			}
		}
		
	for (int i=1;i<=n;i++)
		for (int j=0;j<=m;j++)
		{
			if (j<v[i]) g[i][j]+=g[i-1][j];
			else 
			{
				g[i][j]+=g[i-1][j-v[i]];
				g[i][j]+=g[i-1][j];
			}
		}
	
	for (int i=1;i<=n;i++)
	{
		for (int k=1;k<=m;k++)
		{
			int sum=0;
			for (int j=0;j<=k;j++)	
			{
				(sum+=f[i-1][j]*g[n-i][k-j]+10)%=10;
			}
			printf("%lld",sum%10);	
		}
		printf("\n");
	}
}
2021/5/8 14:47
加载中...