QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#346679#1882. DrunkardsstudentDLWA 1ms3624kbC++142.0kb2024-03-08 21:07:342024-03-08 21:07:35

Judging History

This is the latest submission verdict.

  • [2024-03-08 21:07:35]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3624kb
  • [2024-03-08 21:07:34]
  • Submitted

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;
}
bool a[M];
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;i<=n;i++) read(a[i]);
    reverse(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        int dir=a[i];
        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)%P);
        }
        Add(ans,dp[i][n]);
    }
    write(ans,'\n');
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3616kb

input:

2 28
1 1

output:

702764025

result:

ok 1 number(s): "702764025"

Test #2:

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

input:

5 50
-1 1 -1 -1 -1

output:

952869610

result:

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