QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #153509 | #2587. 荣誉称号 | eikki | 0 | 0ms | 0kb | C++20 | 1.6kb | 2023-08-30 09:17:38 | 2023-08-30 09:17:39 |
answer
#include <iostream>
const int mod = 1000000007;
int ex;
int k[5000], pref_k[5001];
int f[1000001], invf[1000001];
int pref_fk[1000001], pref_invfk[1000001];
bool mem[5001]; int cache[5001];
int pow(int a, int e) {
int result = 1;
while (e > 0) {
if (e % 2 == 1) result = (long long) result * a % mod;
a = (long long) a * a % mod;
e /= 2;
}
return result;
}
int dp(int d) {
if (d == 1) return f[k[1]];
if (mem[d]) return cache[d];
int total = (long long) f[pref_k[d]] % mod;
for (int l = 1; l < d; l++) {
int subtr = (long long) f[pref_k[d] - pref_k[l]] * dp(l) % mod;
total = (total - subtr) % mod;
}
mem[d] = true;
return cache[d] = total;
}
int main() {
f[0] = 1; invf[0] = 1;
for (int i = 1; i < 1000001; i++) {
f[i] = (long long) f[i-1] * i % mod;
}
for (int i = 1; i < 1000001; i++) {
invf[i] = pow(f[i], mod - 2);
}
int n, h, sum = 0;
std::cin >> n >> h;
ex = n;
pref_k[0] = 0;
pref_fk[0] = 1;
pref_invfk[0] = 1;
for (int i = 1; i <= h; i++) {
std::cin >> k[i];
pref_k[i] = pref_k[i-1] + k[i];
pref_fk[i] = ((long long)pref_fk[i-1] * f[k[i]]) % mod;
pref_invfk[i] = ((long long)pref_invfk[i-1] * invf[k[i]]) % mod;
ex -= k[i];
}
int total = (long long) f[ex + pref_k[h]];
for (int d = 1; d <= h; d++) {
int subtr = (long long) f[ex + pref_k[h] - pref_k[d]] * dp(d) % mod;
total = (total - subtr) % mod;
}
std::cout << (total + mod) % mod; // don't forget to mod your answer to make it positive!
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
10 100 6 2 100 233935 922673 177972 100 100 50 10 22 68 21 75 14 95 33 60 55 83 1 92 82 65 83 88 99 58 49 82 70 42 2 59 37 20 18 85 98 76 11 67 52 28 73 66 28 24 49 98 50 1 86 78 43 38 22 94 3 35 35 96 74 37 74 64 84 5 34 38 19 58 9 11 52 77 28 48 66 47 29 12 8 49 83 50 20 31 79 43 6 53 6 68 99 11 8...
output:
result:
Test #2:
score: 0
Runtime Error
input:
10 100000 8 50 100000 247575 819409 776601 100 100 89 32 56 35 20 7 49 32 42 55 32 35 24 93 93 90 54 27 5 38 14 56 29 68 10 88 76 99 93 25 21 89 100 79 48 63 81 38 52 35 96 59 12 79 100 55 16 61 90 78 31 16 27 33 22 81 79 67 74 22 60 14 51 63 60 16 27 17 90 85 94 33 16 86 88 89 40 52 37 5 44 15 35 5...
output:
result:
Test #3:
score: 0
Runtime Error
input:
10 1000000 10 100 100000 955891 404406 316093 100 100 35 87 53 20 85 45 70 69 93 53 52 46 11 58 11 23 62 12 32 18 35 76 39 91 78 34 37 89 40 18 93 80 40 88 4 60 68 40 52 25 68 7 58 88 60 70 25 65 38 16 66 89 8 11 69 99 15 70 69 28 33 6 82 8 64 99 57 37 99 85 55 84 65 59 6 67 7 91 64 72 69 76 68 51 5...