QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#62491 | #2811. NoM | yoIA | 100 ✓ | 62ms | 17128kb | C++14 | 2.0kb | 2022-11-19 15:38:41 | 2022-11-19 15:38:43 |
Judging History
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'