QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #56420 | #1426. Exp | tricyzhkx | WA | 3ms | 3860kb | C++14 | 812b | 2022-10-19 13:05:25 | 2022-10-19 13:05:26 |
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;
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: 2ms
memory: 3692kb
input:
2 1 2 0.5000 0.5000
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
2 1 1 0.5000 0.5000
output:
249561089
result:
ok 1 number(s): "249561089"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3812kb
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: 3860kb
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: 3696kb
input:
1 1 1 0.0765 0.9235
output:
299972429
result:
ok 1 number(s): "299972429"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3688kb
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...
output:
521482851
result:
ok 1 number(s): "521482851"
Test #7:
score: -100
Wrong Answer
time: 3ms
memory: 3740kb
input:
1 100 100 0.0048 0.0100 0.0025 0.0254 0.0183 0.0014 0.0188 0.0019 0.0197 0.0171 0.0127 0.0052 0.0038 0.0052 0.0014 0.0016 0.0133 0.0341 0.0014 0.0234 0.0073 0.0001 0.0088 0.0304 0.0032 0.0008 0.0046 0.0236 0.0039 0.0359 0.0023 0.0096 0.0392 0.0169 0.0018 0.0184 0.0051 0.0050 0.0190 0.0053 0.0034 0.0...
output:
417765311
result:
wrong answer 1st numbers differ - expected: '276513735', found: '417765311'