QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#778708#1882. Drunkardsyjs_WA 0ms3908kbC++201.2kb2024-11-24 15:52:362024-11-24 15:52:37

Judging History

你现在查看的是最新测评结果

  • [2024-11-24 15:52:37]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3908kb
  • [2024-11-24 15:52:36]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int mod=998244353;
const int N=5010;
int n,m,s,l,p,a[N],f[N<<1],g[N<<1];
inline int read()
{
	char x=getchar();
	int ans=0;
	while(x<'0'||x>'9')
		x=getchar();
	while(x>='0'&&x<='9')
	{
		ans=(ans<<1)+(ans<<3)+(x^48);
		x=getchar();
	}
	return ans;
}
int qpow(int x,int k)
{
	int ans=1;
	while(k)
	{
		if(k&1)
			ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;
		k>>=1;
	}
	return ans;
}
void add(int &x,int y)
{
	x=(x+=y)>=mod?x-mod:x;
}
int main()
{
	n=read(),p=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	f[n]=1;
	int pstop=(ll)p*qpow(100,mod-2)%mod;
	int pgo=(1-pstop+mod)%mod;
	for(int i=1;i<=n;i++)
	{
		memcpy(g,f,sizeof(g));
		memset(f,0,sizeof(f));
		for(int j=0;j<=2*n;++j)
		{
			if(!g[j])
				continue;
			add(f[j],(ll)g[j]*pstop%mod);
			add(f[j+a[i]],(ll)g[j]*pgo%mod);
		}
		f[n]=1; 
//		cout<<"I"<<i<<endl;
//		for(int j=0;j<=2*n;j++)
//		{
//			cout<<j<<" "<<f[j]<<endl;
//		}
	}
	int ans=0;
	for(int i=0;i<=2*n;i++)
		add(ans,f[i]);
//	cout<<ans<<endl;
	ans=(ll)ans*qpow(2*n+1,mod-2)%mod;
	printf("%d\n",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3892kb

input:

2 28
1 1

output:

702764025

result:

ok 1 number(s): "702764025"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3908kb

input:

5 50
-1 1 -1 -1 -1

output:

952869610

result:

wrong answer 1st numbers differ - expected: '17015529', found: '952869610'