QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#868152#8728. TablicaKiharaTouma#100 ✓145ms285376kbC++231.1kb2025-01-24 13:27:452025-01-24 13:27:54

Judging History

This is the latest submission verdict.

  • [2025-01-24 13:27:54]
  • Judged
  • Verdict: 100
  • Time: 145ms
  • Memory: 285376kb
  • [2025-01-24 13:27:45]
  • Submitted

answer

//qoj8728
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 6010;
int n, m;
const ll P = 1e9 + 7;
const ll i2 = 5e8 + 4;
ll C[N][N];
ll fac[N];
ll pw2[N], ipw2[N];
ll ans = 0;

int main(){
	scanf("%d%d", &n, &m);
	C[0][0] = fac[0] = pw2[0] = ipw2[0] = 1;
	for(int i = 1; i <= 2 * max(n, m); ++ i){
		C[i][0] = C[i][i] = 1;
		pw2[i] = pw2[i-1] * 2 % P;
		fac[i] = fac[i-1] * i % P;
		ipw2[i] = ipw2[i-1] * i2 % P;
		for(int j = 1; j < i; ++ j){
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) % P;
		}
	}
	for(int b = 0; b <= n; ++ b){
		for(int d = 0; d <= m; ++ d){
			int a = n - b;
			int c = m - d;
			if(a + b + b != c + d + d){
				continue;
			}
			ll tmp = 0;
			for(int p = 0; p <= min(b, d); ++ p){
				ll tt = (p&1) ? P - 1 : 1;
				tt = tt * C[b][p] % P * C[d][p] % P * fac[p] % P * pw2[p] % P;
				tt = tt * fac[c+d*2-p*2] % P;
				tmp = (tmp + tt) % P;
			}
			tmp = tmp * C[n][b] % P * C[m][d] % P * ipw2[b] % P * ipw2[d] % P;
			// printf("%d %d %lld\n", b, d, tmp);
			ans = (ans + tmp) % P;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 5968kb

input:

5 6

output:

456750

result:

ok 1 number(s): "456750"

Test #2:

score: 10
Accepted
time: 0ms
memory: 3968kb

input:

6 6

output:

5464710

result:

ok 1 number(s): "5464710"

Test #3:

score: 10
Accepted
time: 0ms
memory: 3968kb

input:

3 5

output:

270

result:

ok 1 number(s): "270"

Test #4:

score: 10
Accepted
time: 0ms
memory: 6008kb

input:

3 6

output:

90

result:

ok 1 number(s): "90"

Test #5:

score: 10
Accepted
time: 1ms
memory: 3968kb

input:

4 6

output:

14580

result:

ok 1 number(s): "14580"

Test #6:

score: 10
Accepted
time: 0ms
memory: 3712kb

input:

3 4

output:

270

result:

ok 1 number(s): "270"

Subtask #2:

score: 18
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 18
Accepted
time: 0ms
memory: 8156kb

input:

50 49

output:

750700714

result:

ok 1 number(s): "750700714"

Test #8:

score: 18
Accepted
time: 1ms
memory: 8152kb

input:

50 50

output:

630532893

result:

ok 1 number(s): "630532893"

Test #9:

score: 18
Accepted
time: 1ms
memory: 8016kb

input:

41 34

output:

800856205

result:

ok 1 number(s): "800856205"

Test #10:

score: 18
Accepted
time: 0ms
memory: 8068kb

input:

39 41

output:

541550932

result:

ok 1 number(s): "541550932"

Test #11:

score: 18
Accepted
time: 0ms
memory: 7948kb

input:

38 46

output:

651393374

result:

ok 1 number(s): "651393374"

Test #12:

score: 18
Accepted
time: 0ms
memory: 8024kb

input:

37 39

output:

746919932

result:

ok 1 number(s): "746919932"

Test #13:

score: 18
Accepted
time: 1ms
memory: 8092kb

input:

30 50

output:

214086425

result:

ok 1 number(s): "214086425"

Test #14:

score: 18
Accepted
time: 0ms
memory: 8172kb

input:

50 41

output:

193351204

result:

ok 1 number(s): "193351204"

Test #15:

score: 18
Accepted
time: 0ms
memory: 8132kb

input:

44 32

output:

63855946

result:

ok 1 number(s): "63855946"

Test #16:

score: 18
Accepted
time: 0ms
memory: 8040kb

input:

45 42

output:

266239299

result:

ok 1 number(s): "266239299"

Subtask #3:

score: 31
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 31
Accepted
time: 1ms
memory: 22500kb

input:

199 200

output:

841552647

result:

ok 1 number(s): "841552647"

Test #18:

score: 31
Accepted
time: 0ms
memory: 22388kb

input:

200 200

output:

157842226

result:

ok 1 number(s): "157842226"

Test #19:

score: 31
Accepted
time: 0ms
memory: 22388kb

input:

156 199

output:

216453917

result:

ok 1 number(s): "216453917"

Test #20:

score: 31
Accepted
time: 0ms
memory: 24300kb

input:

161 199

output:

539960909

result:

ok 1 number(s): "539960909"

Test #21:

score: 31
Accepted
time: 0ms
memory: 22384kb

input:

194 160

output:

764024671

result:

ok 1 number(s): "764024671"

Test #22:

score: 31
Accepted
time: 0ms
memory: 22428kb

input:

184 195

output:

117763744

result:

ok 1 number(s): "117763744"

Test #23:

score: 31
Accepted
time: 0ms
memory: 20464kb

input:

152 174

output:

350941677

result:

ok 1 number(s): "350941677"

Test #24:

score: 31
Accepted
time: 1ms
memory: 22408kb

input:

195 186

output:

130526660

result:

ok 1 number(s): "130526660"

Test #25:

score: 31
Accepted
time: 1ms
memory: 20480kb

input:

173 159

output:

754934766

result:

ok 1 number(s): "754934766"

Test #26:

score: 31
Accepted
time: 1ms
memory: 22400kb

input:

194 170

output:

956364877

result:

ok 1 number(s): "956364877"

Subtask #4:

score: 41
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #27:

score: 41
Accepted
time: 141ms
memory: 285376kb

input:

3000 2999

output:

5195706

result:

ok 1 number(s): "5195706"

Test #28:

score: 41
Accepted
time: 145ms
memory: 284484kb

input:

3000 3000

output:

224347336

result:

ok 1 number(s): "224347336"

Test #29:

score: 41
Accepted
time: 129ms
memory: 272404kb

input:

2854 2864

output:

513408195

result:

ok 1 number(s): "513408195"

Test #30:

score: 41
Accepted
time: 123ms
memory: 274696kb

input:

2887 2803

output:

58832696

result:

ok 1 number(s): "58832696"

Test #31:

score: 41
Accepted
time: 114ms
memory: 278032kb

input:

2800 2925

output:

804387597

result:

ok 1 number(s): "804387597"

Test #32:

score: 41
Accepted
time: 126ms
memory: 269880kb

input:

2842 2813

output:

971828715

result:

ok 1 number(s): "971828715"

Test #33:

score: 41
Accepted
time: 116ms
memory: 282744kb

input:

2808 2972

output:

329457042

result:

ok 1 number(s): "329457042"

Test #34:

score: 41
Accepted
time: 122ms
memory: 272408kb

input:

2821 2853

output:

81282690

result:

ok 1 number(s): "81282690"

Test #35:

score: 41
Accepted
time: 132ms
memory: 282588kb

input:

2875 2956

output:

105351485

result:

ok 1 number(s): "105351485"

Test #36:

score: 41
Accepted
time: 125ms
memory: 274512kb

input:

2879 2852

output:

672034506

result:

ok 1 number(s): "672034506"

Extra Test:

score: 0
Extra Test Passed