QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#62491#2811. NoMyoIA100 ✓62ms17128kbC++142.0kb2022-11-19 15:38:412022-11-19 15:38:43

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-19 15:38:43]
  • Judged
  • Verdict: 100
  • Time: 62ms
  • Memory: 17128kb
  • [2022-11-19 15:38:41]
  • Submitted

answer

#include <bits/stdc++.h>
#define forn(i,s,t) for(int i=(s); i<=(t); ++i)
#define form(i,s,t) for(int i=(s); i>=(t); --i)
#define rep(i,s,t) for(int i=(s); i<(t); ++i)
using namespace std;
typedef double f64;
typedef long long i64;
typedef unsigned long long u64;
const int N = 2e3 + 3, M = 2e5 + 4, Mod = 1e9 + 7;
struct mint {
	int r;
	mint() {}
	mint(int _r) : r(_r) {}
	inline friend mint operator + (const mint& A, const mint& B) {
		return mint((A.r + B.r >= Mod) ? (A.r + B.r - Mod) : (A.r + B.r));
	}
	inline friend mint operator - (const mint& A, const mint&B) { return A + mint(Mod - B.r);}
	inline friend mint operator * (const mint& A, const mint& B) { return mint(1ll * A.r * B.r % Mod); } 
	inline friend mint& operator += (mint& A, const mint& B) { return A = A + B; }
	inline friend mint& operator -= (mint& A, const mint& B) { return A = A - B; }
	inline friend mint& operator *= (mint& A, const mint& B) { return A = A * B; }
	inline friend mint q_pow(mint p, int k = Mod - 2) {
		mint r = 1;
		for (; k; k >>= 1, p *= p) (k & 1) && (r *= p, 0);
		return r;
	}
};
mint fac[N << 1], ifac[N << 1];
inline void table(int n = 4e3) {
	fac[0] = 1;
	forn (i, 1, n) fac[i] = fac[i - 1] * mint(i);
	ifac[n] = q_pow(fac[n]);
	form (i, n - 1, 0) ifac[i] = ifac[i + 1] * mint(i + 1);
}
inline mint C(int n, int r) {
	if (n < 0 || r < 0 || n < r) return mint(0);
	return fac[n] * ifac[r] * ifac[n - r];
}
int n, m, sz[N]; mint dp[N][N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	table();
	cin >> n >> m;
	rep (i, 0, m) {
		sz[i + 1] = (i != 0);
		for (int j = i + m; j <= 2 * n; j += m) sz[i + 1] ++ ;
	}
	dp[0][0] = 1;
	int sum = 0;
	forn (j, 1, m) {
		sum += sz[j] / 2;
		forn (i, 0, sum) forn (k, 0, min(sz[j] / 2, i)) 
			dp[i][j] += dp[i - k][j - 1] * C(sz[j], 2 * k) * fac[2 * k] * C(i, k);
	}
	mint ans = 0;
	forn (i, 0, n) if (i & 1) ans -= C(n, i) * fac[2 * n - 2 * i] * dp[i][m];
				   else ans += C(n, i) * fac[2 * n - 2 * i] * dp[i][m];
	cout << ans.r << '\n';
	return 0;
} 
/*
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9
Accepted

Test #1:

score: 9
Accepted
time: 1ms
memory: 3360kb

input:

1 1

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3400kb

input:

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

2 2

output:

16

result:

ok single line: '16'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3400kb

input:

3 1

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3452kb

input:

3 2

output:

288

result:

ok single line: '288'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

3 3

output:

384

result:

ok single line: '384'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3412kb

input:

4 2

output:

9216

result:

ok single line: '9216'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3344kb

input:

4 3

output:

13824

result:

ok single line: '13824'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3468kb

input:

5 1

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3536kb

input:

5 5

output:

2088960

result:

ok single line: '2088960'

Subtask #2:

score: 12
Accepted

Dependency #1:

100%
Accepted

Test #11:

score: 12
Accepted
time: 3ms
memory: 5800kb

input:

99 55

output:

117836331

result:

ok single line: '117836331'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

69 50

output:

427094826

result:

ok single line: '427094826'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3704kb

input:

67 5

output:

733227544

result:

ok single line: '733227544'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3632kb

input:

69 26

output:

730153757

result:

ok single line: '730153757'

Test #15:

score: 0
Accepted
time: 3ms
memory: 3600kb

input:

71 64

output:

100578188

result:

ok single line: '100578188'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

87 10

output:

410973724

result:

ok single line: '410973724'

Test #17:

score: 0
Accepted
time: 3ms
memory: 3780kb

input:

64 35

output:

623989218

result:

ok single line: '623989218'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

67 51

output:

312068739

result:

ok single line: '312068739'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

85 3

output:

796582412

result:

ok single line: '796582412'

Subtask #3:

score: 13
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #20:

score: 13
Accepted
time: 2ms
memory: 6120kb

input:

164 20

output:

152386555

result:

ok single line: '152386555'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3976kb

input:

154 80

output:

741601266

result:

ok single line: '741601266'

Test #22:

score: 0
Accepted
time: 4ms
memory: 4516kb

input:

266 255

output:

245915928

result:

ok single line: '245915928'

Test #23:

score: 0
Accepted
time: 1ms
memory: 4448kb

input:

239 19

output:

511848592

result:

ok single line: '511848592'

Test #24:

score: 0
Accepted
time: 5ms
memory: 4612kb

input:

296 141

output:

462138216

result:

ok single line: '462138216'

Test #25:

score: 0
Accepted
time: 2ms
memory: 4516kb

input:

255 250

output:

727256255

result:

ok single line: '727256255'

Test #26:

score: 0
Accepted
time: 4ms
memory: 4468kb

input:

257 15

output:

253032679

result:

ok single line: '253032679'

Test #27:

score: 0
Accepted
time: 5ms
memory: 4920kb

input:

300 299

output:

559277735

result:

ok single line: '559277735'

Subtask #4:

score: 18
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #28:

score: 18
Accepted
time: 7ms
memory: 5968kb

input:

625 19

output:

787742499

result:

ok single line: '787742499'

Test #29:

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

input:

657 324

output:

660247748

result:

ok single line: '660247748'

Test #30:

score: 0
Accepted
time: 7ms
memory: 6444kb

input:

646 582

output:

830442831

result:

ok single line: '830442831'

Test #31:

score: 0
Accepted
time: 3ms
memory: 5964kb

input:

637 14

output:

468904506

result:

ok single line: '468904506'

Test #32:

score: 0
Accepted
time: 6ms
memory: 6776kb

input:

685 343

output:

516203560

result:

ok single line: '516203560'

Test #33:

score: 0
Accepted
time: 12ms
memory: 6768kb

input:

713 644

output:

225559251

result:

ok single line: '225559251'

Test #34:

score: 0
Accepted
time: 15ms
memory: 8600kb

input:

900 899

output:

941929065

result:

ok single line: '941929065'

Subtask #5:

score: 48
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #35:

score: 48
Accepted
time: 26ms
memory: 9980kb

input:

1624 18

output:

887332511

result:

ok single line: '887332511'

Test #36:

score: 0
Accepted
time: 45ms
memory: 14716kb

input:

1779 1687

output:

611283083

result:

ok single line: '611283083'

Test #37:

score: 0
Accepted
time: 24ms
memory: 9896kb

input:

1603 18

output:

846564825

result:

ok single line: '846564825'

Test #38:

score: 0
Accepted
time: 29ms
memory: 12516kb

input:

1651 818

output:

148850576

result:

ok single line: '148850576'

Test #39:

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

input:

1579 1501

output:

427262684

result:

ok single line: '427262684'

Test #40:

score: 0
Accepted
time: 62ms
memory: 17128kb

input:

2000 1999

output:

510859110

result:

ok single line: '510859110'