QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#829465#4542. Cyber PainterDaiRuiChen007AC ✓1506ms26996kbC++171.5kb2024-12-24 10:15:222024-12-24 10:15:24

Judging History

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

  • [2024-12-24 10:15:24]
  • 评测
  • 测评结果:AC
  • 用时:1506ms
  • 内存:26996kb
  • [2024-12-24 10:15:22]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5,MOD=1e9+7;
ll fac[MAXN],ifac[MAXN],inv[MAXN];
ll ksm(ll a,ll b=MOD-2) { ll s=1; for(;b;a=a*a%MOD,b>>=1) if(b&1) s=s*a%MOD; return s; }
int n,m,a[16];
ll A(int x,int y) {
	if(x<0||y<0||y>x) return 0;
	return fac[x]*ifac[x-y]%MOD;
}
ll C(int x,int y) {
	if(x<0||y<0||y>x) return 0;
	return fac[x]*ifac[x-y]%MOD*ifac[y]%MOD;
}
ll f(int k,int x,int y,int z) {
	ll s=0;
	for(int i=max(k-x,0);i<=z&&i<=k&&y+z-i>=k;++i) {
		s=(s+A(z,i)*A(x,k-i)%MOD*C(k,i)%MOD*A(y+z-i,k))%MOD;
	}
	return s;
}
void solve() {
	cin>>n>>m;
	for(int i=0;i<16;++i) cin>>a[i];
	ll ans=0;
	for(int i=0;i<min(n,m);++i) {
		ll p=0,w=ifac[n*m]*fac[n*m-4*(i+1)]%MOD;
		for(int s1:{9,11,13,15}) if(a[s1]) {
			w=w*(a[s1]--)%MOD;
			for(int s2:{12,13,14,15}) if(a[s2]) {
				w=w*(a[s2]--)%MOD;
				for(int s3:{6,7,14,15}) if(a[s3]) {
					w=w*(a[s3]--)%MOD;
					for(int s4:{3,7,11,15}) if(a[s4]) {
						w=w*(a[s4]--)%MOD;
						p=(p+w*f(2*i,a[5]+a[7]+a[13],a[10]+a[11]+a[14],a[15]))%MOD;
						w=w*inv[++a[s4]]%MOD;
					}
					w=w*inv[++a[s3]]%MOD;
				}
				w=w*inv[++a[s2]]%MOD;
			}
			w=w*inv[++a[s1]]%MOD;
		}
		ans=(ans+p*(n-i-1)*(m-i-1))%MOD;
	}
	cout<<ans<<"\n";
}
signed main() {
	inv[1]=1;
	for(int i=2;i<MAXN;++i) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
	for(int i=fac[0]=ifac[0]=1;i<MAXN;++i) fac[i]=fac[i-1]*i%MOD,ifac[i]=ifac[i-1]*inv[i]%MOD;
	ios::sync_with_stdio(false);
	int T; cin>>T;
	while(T--) solve();
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1506ms
memory: 26996kb

input:

10000
2 1
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
3 1
1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
1 1
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
1 1
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
1 3
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 3
0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0
1 2
1 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
597798962
194245930
834284364
543970328
906286314
479624062
0
0
0
466666670
604761909
0
496428575
0
0
384954093
0
942128054
0
57644305
0
407142860
0
0
0
903001318
0
0
611739135
303696306
189542485
0
38720539
0
0
0
708377124
0
0
205555557
0
0
296078035
0
380854853
0
0
0
146969...

result:

ok 10000 lines