萌新求助,这会T ??
查看原帖
萌新求助,这会T ??
415256
Epoch_L楼主2022/8/27 21:26

求大佬帮调,这不应该70分吗,怎么从 subtask2 开始就 T 了?

#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
	char ch=getchar();
	int r=0,w=1;
	while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
	while(isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
	x=r*w;
}
const int N=501,M=101,mod=998244353;
int f[N][N][M],g[N][N][M],L[N],R[N];
int mul(int x,int y)
{
	int ans=0;
	while(y)
	{
		if(y&1)ans=(ans+x)%mod;
		x=x*2%mod;
		y>>=1;
	}
	return ans;
}
int main()
{
	int n,q;
	read(n);read(q);
	for(int i=1;i<=n;i++)
		read(L[i]),read(R[i]);
	for(int i=1;i<=n;i++)
		f[i][i][0]=g[i][i][0]=1;
	for(int k=1;k<=100;k++)
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[i][L[j]][k]=(f[i][L[j]][k]+f[i][j][k-1])%mod;
			f[i][R[j]+1][k]=(f[i][R[j]+1][k]-f[i][j][k-1]+mod)%mod;
			g[i][L[j]][k]=(g[i][L[j]][k]+g[i][j][k-1])%mod;
			g[i][R[j]+1][k]=(g[i][R[j]+1][k]-g[i][j][k-1]+mod)%mod;
		}
		for(int j=1;j<=n;j++)
			f[i][j][k]=(f[i][j][k]+f[i][j-1][k])%mod,
			g[i][j][k]=(g[i][j][k]+g[i][j-1][k])%mod;
		g[i][i][k]=0;
	}
	while(q--)
	{
		int a,b,c,m;
		read(a);read(b);read(c);read(m);
		int ans=f[a][b][m];
		for(int i=0;i<=m;i++)ans=(ans-mul(f[a][c][i],g[c][b][m-i])+mod)%mod;
		printf("%d\n",ans);
	}
	return 0;
}
2022/8/27 21:26
加载中...