QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291153 | #2153. HILO | MoRanSky | 100 ✓ | 69ms | 3968kb | C++23 | 1.9kb | 2023-12-26 05:06:59 | 2023-12-26 05:07:00 |
Judging History
answer
// Skyqwq
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N = 5e3 + 5, P = 1e9 + 7;
int n, x, fact[N], infact[N], f[N], g[N];
int inline power(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = (LL)res * a % P;
a = (LL)a * a % P;
b >>= 1;
}
return res;
}
void inline add(int &x, int y) {
x += y;
if (x >= P) x -= P;
}
void inline factPrework(int n) {
fact[0] = infact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = (LL)fact[i - 1] * i % P;
infact[n] = power(fact[n], P - 2);
for (int i = n - 1; i; i--) infact[i] = infact[i + 1] * (i + 1ll) % P;
}
int inline C(int a, int b) {
if (a < b || a < 0 || b < 0) return 0;
return (LL)fact[a] * infact[b] % P * infact[a - b] % P;
}
int inv2 = (P + 1) / 2;
int main() {
factPrework(5e3 + 1);
read(n), read(x);
int ans = 0;
for (int i = 0; i < n - x; i++) {
for (int j = 0; j < x; j++) {
if (!j) add(ans, 1ll * fact[i + 1] * C(n - x, i + 1) % P * C(x, j + 1) % P * fact[n - i - j - 2] % P);
else {
int gx = 1ll * fact[i + j + 1] * inv2 % P;
add(ans, 1ll * gx * C(n - x, i + 1) % P * C(x, j + 1) % P * fact[n - i - j - 2] % P);
}
}
}
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 3.84615
Accepted
time: 0ms
memory: 3908kb
input:
4 2
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 3.84615
Accepted
time: 0ms
memory: 3800kb
input:
60 10
output:
508859913
result:
ok 1 number(s): "508859913"
Test #3:
score: 3.84615
Accepted
time: 0ms
memory: 3772kb
input:
36 2
output:
653172943
result:
ok 1 number(s): "653172943"
Test #4:
score: 3.84615
Accepted
time: 0ms
memory: 3868kb
input:
38 12
output:
877759561
result:
ok 1 number(s): "877759561"
Test #5:
score: 3.84615
Accepted
time: 0ms
memory: 3968kb
input:
40 22
output:
587738552
result:
ok 1 number(s): "587738552"
Test #6:
score: 3.84615
Accepted
time: 0ms
memory: 3824kb
input:
42 9
output:
142300060
result:
ok 1 number(s): "142300060"
Test #7:
score: 3.84615
Accepted
time: 0ms
memory: 3784kb
input:
44 42
output:
194449602
result:
ok 1 number(s): "194449602"
Test #8:
score: 3.84615
Accepted
time: 0ms
memory: 3868kb
input:
46 41
output:
996298696
result:
ok 1 number(s): "996298696"
Test #9:
score: 3.84615
Accepted
time: 0ms
memory: 3884kb
input:
48 16
output:
933315069
result:
ok 1 number(s): "933315069"
Test #10:
score: 3.84615
Accepted
time: 0ms
memory: 3804kb
input:
50 1
output:
592235889
result:
ok 1 number(s): "592235889"
Test #11:
score: 3.84615
Accepted
time: 0ms
memory: 3872kb
input:
106 25
output:
370147128
result:
ok 1 number(s): "370147128"
Test #12:
score: 3.84615
Accepted
time: 0ms
memory: 3772kb
input:
162 125
output:
588210522
result:
ok 1 number(s): "588210522"
Test #13:
score: 3.84615
Accepted
time: 1ms
memory: 3784kb
input:
218 196
output:
722904144
result:
ok 1 number(s): "722904144"
Test #14:
score: 3.84615
Accepted
time: 1ms
memory: 3836kb
input:
275 77
output:
201201377
result:
ok 1 number(s): "201201377"
Test #15:
score: 3.84615
Accepted
time: 1ms
memory: 3844kb
input:
331 195
output:
105599195
result:
ok 1 number(s): "105599195"
Test #16:
score: 3.84615
Accepted
time: 1ms
memory: 3788kb
input:
387 160
output:
51654417
result:
ok 1 number(s): "51654417"
Test #17:
score: 3.84615
Accepted
time: 1ms
memory: 3876kb
input:
443 407
output:
973597938
result:
ok 1 number(s): "973597938"
Test #18:
score: 3.84615
Accepted
time: 1ms
memory: 3808kb
input:
500 196
output:
279036314
result:
ok 1 number(s): "279036314"
Test #19:
score: 3.84615
Accepted
time: 69ms
memory: 3792kb
input:
4944 2238
output:
373098474
result:
ok 1 number(s): "373098474"
Test #20:
score: 3.84615
Accepted
time: 51ms
memory: 3864kb
input:
4952 3750
output:
127862445
result:
ok 1 number(s): "127862445"
Test #21:
score: 3.84615
Accepted
time: 66ms
memory: 3872kb
input:
4960 2465
output:
524400159
result:
ok 1 number(s): "524400159"
Test #22:
score: 3.84615
Accepted
time: 67ms
memory: 3876kb
input:
4968 3013
output:
429923833
result:
ok 1 number(s): "429923833"
Test #23:
score: 3.84615
Accepted
time: 68ms
memory: 3844kb
input:
4976 2108
output:
909616241
result:
ok 1 number(s): "909616241"
Test #24:
score: 3.84615
Accepted
time: 63ms
memory: 3908kb
input:
4984 1656
output:
572267695
result:
ok 1 number(s): "572267695"
Test #25:
score: 3.84615
Accepted
time: 54ms
memory: 3960kb
input:
4992 3695
output:
824711289
result:
ok 1 number(s): "824711289"
Test #26:
score: 3.84615
Accepted
time: 12ms
memory: 3792kb
input:
5000 207
output:
765133070
result:
ok 1 number(s): "765133070"