QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

你现在查看的是最新测评结果

[2024-07-15 17:47:09]
评测

测评结果：WA
用时：2ms
内存：10648kb

查看

[2024-07-15 17:47:08]
提交

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


*/

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 10648kb

input:

2 2
1 1
1 1

output:

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:

result:

wrong answer expected '5', found '0'