QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#778722#1882. Drunkardsyjs_WA 0ms3900kbC++201.2kb2024-11-24 15:57:552024-11-24 15:57:55

Judging History

This is the latest submission verdict.

  • [2024-11-24 15:57:55]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3900kb
  • [2024-11-24 15:57:55]
  • Submitted

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);
			if(0<=j+a[i]&&j+a[i]<=2*n)
				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);
}

詳細信息

Test #1:

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

input:

2 28
1 1

output:

702764025

result:

ok 1 number(s): "702764025"

Test #2:

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

input:

5 50
-1 1 -1 -1 -1

output:

952869610

result:

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