QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#345439#1882. DrunkardsstudentDLWA 1ms3644kbC++141.9kb2024-03-06 22:53:302024-03-06 22:53:30

Judging History

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

  • [2024-03-06 22:53:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3644kb
  • [2024-03-06 22:53:30]
  • 提交

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'