QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #56421 | #1426. Exp | tricyzhkx | RE | 2ms | 3784kb | C++14 | 893b | 2022-10-19 13:19:40 | 2022-10-19 13:19:42 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int mod=998244353,_10000=796898467;
typedef long long ll;
ll inv[10000010];
int g[110],f[10000010];
ll power(ll a,int b)
{
ll ans=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) ans=ans*a%mod;
return ans;
}
int main()
{
int n,K,m,ans=0;
double p;
cin>>n>>K>>m;
inv[0]=inv[1]=1;
for(int i=2;i<=m;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=0;i<=K;i++) scanf("%lf",&p),g[i]=(ll)(p*10000)*_10000%mod;
int sss=0;
for(int i=0;i<=K;i++) sss=(sss+g[i])%mod;
assert(sss==1);
f[0]=power(g[0],n);f[m]=1-f[0]+mod;
int iv=power(g[0],mod-2);
for(int i=1;i<m;i++)
{
for(int j=1;j<=min(i,K);j++) f[i]=(f[i]+g[j]*((ll)(n+1)*j%mod-i+mod)%mod*f[i-j])%mod;
f[i]=f[i]*inv[i]%mod*iv%mod;
ans=(ans+(ll)f[i]*i)%mod;
f[m]=(f[m]-f[i]+mod)%mod;
}
ans=(ans+(ll)f[m]*m)%mod;
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3692kb
input:
2 1 2 0.5000 0.5000
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
2 1 1 0.5000 0.5000
output:
249561089
result:
ok 1 number(s): "249561089"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
4 2 5 0.2000 0.5000 0.3000
output:
909700083
result:
ok 1 number(s): "909700083"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
10 4 23 0.4533 0.2906 0.1618 0.0071 0.0872
output:
433575862
result:
ok 1 number(s): "433575862"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
1 1 1 0.0765 0.9235
output:
299972429
result:
ok 1 number(s): "299972429"
Test #6:
score: -100
Dangerous Syscalls
input:
1 100 1 0.0072 0.0153 0.0002 0.0067 0.0035 0.0030 0.0013 0.0025 0.0090 0.0100 0.0173 0.0018 0.0072 0.0037 0.0078 0.0060 0.0083 0.0054 0.0069 0.0002 0.0143 0.0132 0.0101 0.0027 0.0167 0.0065 0.0051 0.0001 0.0175 0.0079 0.0107 0.0018 0.0017 0.0031 0.0130 0.0108 0.0050 0.0045 0.0322 0.0040 0.0043 0.009...