QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#345439 | #1882. Drunkards | studentDL | WA | 1ms | 3644kb | C++14 | 1.9kb | 2024-03-06 22:53:30 | 2024-03-06 22:53:30 |
Judging History
answer
#include<algorithm>
#include<cstdio>
#include<cstring>
#define pii pair<int,int>
#define mk make_pair
#define ft first
#define se second
#define pb push_back
#define db double
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define inf 1e18
using namespace std;
namespace IO{
#ifndef LOCAL
#define SIZE 30000
char in[SIZE],out[SIZE],*p1=in,*p2=in,*p3=out;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,SIZE,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(p3=out,1,SIZE,stdout))
#define putchar(ch) (p3==out+SIZE&&flush(),*p3++=(ch))
class Flush{public:~Flush(){fwrite(out,1,p3-out,stdout);}}_;
#endif
template<typename type>
inline void read(type &x){
x=0;bool flag=0;char ch=getchar();
while(ch<'0'||ch>'9') flag^=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
flag?x=-x:0;
}
template<typename type>
inline void write(type x,char ch=0){
x<0?x=-x,putchar('-'):0;static short Stack[50],top=0;
do Stack[++top]=x%10,x/=10;while(x);
while(top) putchar(Stack[top--]|48);
if(ch) putchar(ch);
}
}
using namespace IO;
#define M 5005
#define P 998244353
void Add(int &x,int y){
x+y>=P?x+=y-P:x+=y;
}
int n,p,dp[M][M<<1];
int qpow(int b,int p){
int res=1;
while(p){
if(p&1) res=1ll*res*b%P;
b=1ll*b*b%P,p>>=1;
}
return res;
}
int main(){
read(n),read(p);
p=1ll*p*qpow(100,P-2)%P;
int ini=qpow(2*n+1,P-2),ans=ini;
for(int i=0;i<=2*n;i++) dp[0][i]=ini;
for(int i=1,dir;i<=n;i++){
read(dir);
for(int j=0;j<=2*n;j++){
if(j==n) continue;
Add(dp[i][j],1ll*dp[i-1][j]*p%P);
if(j+dir>0&&j+dir<=2*n) Add(dp[i][j+dir],1ll*dp[i-1][j]*(1-p)%P);
}
Add(ans,dp[i][n]);
}
write(ans,'\n');
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
2 28 1 1
output:
702764025
result:
ok 1 number(s): "702764025"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
5 50 -1 1 -1 -1 -1
output:
17015529
result:
ok 1 number(s): "17015529"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3644kb
input:
5 50 -1 1 -1 1 1
output:
982611034
result:
wrong answer 1st numbers differ - expected: '680621150', found: '982611034'