NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #202058 | #3521. Draw a Card | shr | 100 | 2350ms | 49136kb | C++11 | 1.4kb | 2024-02-11 08:55:33 | 2024-02-11 13:09:18 |
answer
#include<bits/stdc++.h>
using namespace std;const int mod=998244353;int qpow(int a,int b){int c=1;for(;b;b>>=1){if(b&1)c=1ll*a*c%mod;a=1ll*a*a%mod;}return c;}const int N=1e6;int jc[N+10],ij[N+10],tp[N+10],inv[N+10];void sieve(){jc[0]=1;for(int i=1;i<=N;i++)jc[i]=1ll*i*jc[i-1]%mod;ij[N]=qpow(jc[N],mod-2);for(int i=N;i;i--)ij[i-1]=1ll*i*ij[i]%mod;inv[1]=1;for(int i=2;i<=N;i++)inv[i]=mod-1ll*inv[mod%i]*(mod/i)%mod;for(int i=1;i<=N;i++)tp[i]=(tp[i-1]+inv[i])%mod;}int C(int a,int b){if(a<b||a<0||b<0)return 0;return 1ll*jc[a]*ij[b]%mod*ij[a-b]%mod;}int n,m,a[20],b[20],ot[20];int f[1<<12][1010],g[1<<12][1010];int main(){sieve();scanf("%d%d",&n,&m);int pb=0,so=0;for(int i=0;i<m;i++)scanf("%d",&a[i]);for(int i=0;i<m;i++){scanf("%d",&b[i]),pb+=b[i],ot[i]=1ll*jc[a[i]]*ij[a[i]-b[i]]%mod;if(!b[i])so|=(1<<i);}g[so][0]=1;for(int s=0;s<(1<<m);s++){int ts=0,bs=0;for(int i=0;i<m;i++)if((s>>i)&1)ts+=a[i]-b[i],bs+=b[i];for(int x=0;x<m;x++)if(!((s>>x)&1)&&b[x]){int s1=0,s2=0,s4=0;for(int i=0;i<=min(pb,n-ts);i++){if(i){int ob=1ll*jc[n-i-ts]*ot[x]%mod*C(i-1-bs,b[x]-1)%mod;(f[s|(1<<x)][i]+=1ll*ob*s1%mod)%=mod;(f[s|(1<<x)][i]+=1ll*ob*s2%mod*ts%mod)%=mod;(f[s|(1<<x)][i]-=1ll*ob*tp[n-i-ts]%mod*ts%mod*s4%mod)%=mod;(g[s|(1<<x)][i]+=1ll*ob*s4%mod)%=mod;}(s1+=1ll*ij[n-i-ts]*f[s][i]%mod)%=mod;(s2+=1ll*ij[n-i-ts]*g[s][i]%mod*tp[n-i-ts]%mod)%=mod;(s4+=1ll*ij[n-i-ts]*g[s][i]%mod)%=mod;}}}printf("%d\n",((f[(1<<m)-1][pb]%mod+mod)%mod+pb)%mod);return 0;}
详细
小提示：点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 32ms
memory: 16864kb
input:
300 3 94 108 98 21 6 24
output:
429514955
result:
ok 1 number(s): "429514955"
Test #2:
score: 0
Accepted
time: 23ms
memory: 16876kb
input:
300 3 114 87 99 17 73 0
output:
373612158
result:
ok 1 number(s): "373612158"
Test #3:
score: 0
Accepted
time: 24ms
memory: 16844kb
input:
300 2 160 140 83 43
output:
607272497
result:
ok 1 number(s): "607272497"
Subtask #2:
score: 20
Accepted
Test #4:
score: 20
Accepted
time: 22ms
memory: 17312kb
input:
20 6 2 5 2 3 2 6 2 1 2 0 1 2
output:
102890512
result:
ok 1 number(s): "102890512"
Test #5:
score: 0
Accepted
time: 23ms
memory: 24648kb
input:
20 10 2 1 1 2 2 3 2 2 0 5 0 1 0 1 0 1 1 2 0 0
output:
349385555
result:
ok 1 number(s): "349385555"
Test #6:
score: 0
Accepted
time: 28ms
memory: 49088kb
input:
20 12 1 1 2 0 1 3 2 3 2 1 3 1 1 0 2 0 1 3 2 2 0 1 2 1
output:
353363623
result:
ok 1 number(s): "353363623"
Test #7:
score: 0
Accepted
time: 27ms
memory: 16928kb
input:
20 4 7 3 6 4 5 2 6 3
output:
395691825
result:
ok 1 number(s): "395691825"
Subtask #3:
score: 15
Accepted
Test #8:
score: 15
Accepted
time: 31ms
memory: 16928kb
input:
30 4 6 7 9 8 2 5 6 3
output:
60666143
result:
ok 1 number(s): "60666143"
Test #9:
score: 0
Accepted
time: 33ms
memory: 17304kb
input:
30 6 6 3 4 7 4 6 4 0 2 3 0 3
output:
630806734
result:
ok 1 number(s): "630806734"
Test #10:
score: 0
Accepted
time: 32ms
memory: 24888kb
input:
30 10 1 1 1 2 4 2 9 3 4 3 1 1 1 1 2 1 6 3 2 0
output:
179858440
result:
ok 1 number(s): "179858440"
Test #11:
score: 0
Accepted
time: 39ms
memory: 49100kb
input:
30 12 3 3 4 3 1 2 3 2 3 2 1 3 1 0 4 1 1 0 1 1 1 1 1 0
output:
301187770
result:
ok 1 number(s): "301187770"
Test #12:
score: 0
Accepted
time: 31ms
memory: 20748kb
input:
30 9 3 4 6 3 5 1 2 4 2 3 0 3 2 0 1 0 0 2
output:
436026962
result:
ok 1 number(s): "436026962"
Subtask #4:
score: 10
Accepted
Test #13:
score: 10
Accepted
time: 50ms
memory: 49084kb
input:
50 12 1 7 2 5 7 2 5 5 1 4 8 3 0 3 1 0 7 2 4 0 1 1 2 1
output:
239294646
result:
ok 1 number(s): "239294646"
Test #14:
score: 0
Accepted
time: 23ms
memory: 32872kb
input:
50 11 2 8 8 4 4 2 3 8 5 1 5 1 3 0 1 0 2 3 1 0 0 2
output:
765549051
result:
ok 1 number(s): "765549051"
Test #15:
score: 0
Accepted
time: 31ms
memory: 17812kb
input:
50 7 8 8 4 8 7 6 9 2 0 2 0 4 4 3
output:
549208280
result:
ok 1 number(s): "549208280"
Test #16:
score: 0
Accepted
time: 31ms
memory: 18824kb
input:
50 8 7 7 9 6 5 2 9 5 6 4 3 4 2 1 0 5
output:
839273742
result:
ok 1 number(s): "839273742"
Subtask #5:
score: 10
Accepted
Test #17:
score: 10
Accepted
time: 35ms
memory: 17312kb
input:
1000 6 163 186 169 133 180 169 22 107 126 110 157 76
output:
157453508
result:
ok 1 number(s): "157453508"
Test #18:
score: 0
Accepted
time: 33ms
memory: 17060kb
input:
1000 5 207 204 201 189 199 186 78 40 43 44
output:
883958433
result:
ok 1 number(s): "883958433"
Test #19:
score: 0
Accepted
time: 37ms
memory: 17320kb
input:
1000 6 199 154 146 162 174 165 189 144 141 159 169 157
output:
979732021
result:
ok 1 number(s): "979732021"
Subtask #6:
score: 35
Accepted
Test #20:
score: 35
Accepted
time: 811ms
memory: 49128kb
input:
1000 12 83 77 95 76 81 104 78 79 75 96 71 85 73 77 90 76 74 95 71 79 67 93 63 84
output:
286972637
result:
ok 1 number(s): "286972637"
Test #21:
score: 0
Accepted
time: 454ms
memory: 49128kb
input:
1000 12 93 77 93 91 87 70 94 70 78 92 72 83 2 30 13 87 61 11 30 27 57 47 65 51
output:
683836742
result:
ok 1 number(s): "683836742"
Test #22:
score: 0
Accepted
time: 500ms
memory: 49136kb
input:
1000 12 85 92 75 75 83 90 89 76 80 84 87 84 52 86 59 34 0 41 35 64 63 57 65 66
output:
100350235
result:
ok 1 number(s): "100350235"
Extra Test:
score: 0
Extra Test Passed
