QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #479475 | #7754. Rolling For Days | ucup-team052# | WA | 2ms | 10648kb | C++14 | 2.2kb | 2024-07-15 17:47:08 | 2024-07-15 17:47:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
inline int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y) {return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y) {return 1LL*x*y%mod;}
inline int mul(int x,int y,int z) {return mul(mul(x,y),z);}
#define inc(x,y) x=add(x,y)
#define N 12
int a[N],b[N],f[1<<N][1005],g[1<<N][1005];
int C[1005][1005],sum[1<<N],n,m;
int sa[1<<N];
int inv[1005],fac[1005];
signed main() {
#ifdef xay5421
freopen("b.in","r",stdin);
#endif
cin>>n>>m;
for(int i=0;i<m;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
C[0][0]=1;
for(int i=1;i<=1000;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++) C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
fac[0]=1; for(int i=1;i<=1000;i++) fac[i]=mul(fac[i-1],i);
inv[0]=inv[1]=1; for(int i=2;i<=1000;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
f[0][0]=1;
for(int i=0;i<1<<m;i++)
{
for(int j=0;j<m;j++) if(i>>j&1) sum[i]+=b[j];
}
for(int i=0;i<1<<m;i++)
{
for(int j=0;j<m;j++) if(i>>j&1) sa[i]+=a[j];
}
int ful=(1<<m)-1;
for(int st=0;st<1<<m;st++)
{
for(int i=0;i<=n;i++)if(i<=sa[st^ful])
{
int NA=mul(n-sum[st]-i,inv[sa[st^ful]-i]);
int ti=inv[n-sa[st]-i];
{ // add 1
f[st][i+1]=add(f[st][i+1],mul(f[st][i],ti));
g[st][i+1]=add(g[st][i+1],mul(g[st][i],ti));
int nw=mul(f[st][i],NA);
inc(g[st][i+1],mul(nw,ti));
}
{ // boom
for(int j=0;j<m;j++) if(!(st>>j&1))
{
if(i<b[j]-1) continue;
int cw=mul(f[st][i],C[i][b[j]-1]);
inc(f[st|(1<<j)][i-b[j]+1],mul(cw,ti));
inc(g[st|(1<<j)][i-b[j]+1],mul(g[st][i],C[i][b[j]-1],ti));
inc(g[st|(1<<j)][i-b[j]+1],mul(NA,cw,ti));
}
}
}
}
// for(int i=0;i<1<<m;i++) for(int j=0;j<=n;j++) printf("%d%c",f[i][j]," \n"[j==n]);
// for(int i=0;i<1<<m;i++) for(int j=0;j<=n;j++) printf("%d%c",g[i][j]," \n"[j==n]);
int ans=g[ful][0];
for(int i=0;i<m;i++) for(int j=0;j<b[i];j++) ans=mul(ans,a[i]-j);
// for(int i=0;i<sum[ful];i++) ans=mul(ans,inv[n-i]);
cout<<ans<<endl;
return 0;
}
/*
1 1 1 1 1
1 3 6 10 10
1 2 3 4 5
3 12 30 60 70
0 1 2 3 4
2 9 24 40 40
1 499122181 499122188 499122195 499122199
499122188 499122232 135 265 305
415935149
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10648kb
input:
2 2 1 1 1 1
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 10548kb
input:
4 2 2 2 2 1
output:
582309210
result:
ok answer is '582309210'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 10144kb
input:
5 5 1 1 1 1 1 0 0 0 0 1
output:
0
result:
wrong answer expected '5', found '0'