莫名其妙TLE
  • 板块学术版
  • 楼主erok
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/10/7 13:45
  • 上次更新2023/10/27 08:20:07
查看原帖
莫名其妙TLE
655791
erok楼主2022/10/7 13:45
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int maxn=2e5+5;
int n,k;
int dp[2][maxn];
int ans[maxn],pre[maxn];
signed main() {
	cin>>n>>k;
	dp[0][0]=1;
	int cnt=k,m=0,x=0;
	while(x<=n)
		x+=cnt,cnt++,m++;
	for(int i=1; i<=m; i++) {
		memset(pre,0,sizeof(pre));
		for(int j=0; j<=n; j++) {
			if(j>=(k+i-1)) {
				pre[j]=pre[j-(k+i-1)]+dp[(i-1)&1][j];
				pre[j]%=mod;
			} else {
				pre[j]=dp[(i-1)&1][j];
				pre[j]%=mod;
			}
		}
		for(int j=0; j<=n; j++) {
			if(j>=(k+i-1)) {
				dp[i&1][j]+=pre[j-(k+i-1)];
				dp[i&1][j]%=mod;
			}
		}
		for(int j=1; j<=n; j++) {
			dp[(i-1)&1][j]=0;
			for(int j=1; j<=n; j++) {
				ans[j]+=dp[i&1][j];
				ans[j]%=mod;
			}
		}
	}
	for(int i=1; i<=n; i++) printf("%lld ",ans[i]);
}

RTRTnn最大2e5,理论复杂度约九千万,但在时限两秒的CF机子T了

2022/10/7 13:45
加载中...