QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#440982 | #6756. 桂花树 | Max_s_xaM | 100 ✓ | 285ms | 29264kb | C++14 | 3.1kb | 2024-06-14 08:26:57 | 2024-06-14 08:26:58 |
Judging History
answer
#include <iostream>
#include <algorithm>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 3010, MAXM = 1050, mod = 1e9 + 7;
int n, m, k;
ll f[MAXN][MAXM];
int main()
{
// freopen("B.in", "r", stdin);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
int CASE, T; Read(CASE), Read(T);
while (T--)
{
Read(n), Read(m), Read(k);
for (int i = 2, x; i <= n; i++) Read(x);
for (int i = 0; i <= m; i++)
for (int s = 0; s < (1 << k); s++)
f[i][s] = 0;
f[0][0] = 1;
for (int i = 0, sz; i < m; i++)
for (int s = 0; s < (1 << k); s++)
{
if (!f[i][s]) continue;
sz = n + i + __builtin_popcount(s);
if (!(s & 1) || !k)
{
(f[i + 1][s >> 1] += f[i][s] * (2 * sz - 1)) %= mod;
if (k) (f[i + 1][s >> 1 | (1 << k - 1)] += f[i][s] * (sz - 1)) %= mod;
for (int j = 0; j < k; j++)
if (s & (1 << j)) (f[i + 1][(s ^ (1 << j)) >> 1] += f[i][s]) %= mod;
}
else (f[i + 1][s >> 1] += f[i][s]) %= mod;
}
cout << f[m][0] << '\n';
}
return 0;
}
详细
Test #1:
score: 5
Accepted
time: 1ms
memory: 3652kb
input:
1 15 4 2 9 1 2 3 4 4 1 1 1 1 4 3 10 1 2 3 4 2 10 1 2 3 2 3 0 1 2 2 8 1 2 4 10 1 3 3 0 1 2 3 2 0 1 1 2 2 0 1 2 4 9 1 4 2 0 1 1 1 2 4 1 1 4 4 8 1 1 1 3 3 0 1 2
output:
66 10132 787 66 105 16 1296 315 35 15 1296 63 1110 11384 315
result:
ok 15 numbers
Test #2:
score: 5
Accepted
time: 0ms
memory: 3624kb
input:
2 15 4 2 0 1 1 1 3 4 8 1 2 2 2 9 1 3 4 0 1 1 4 2 9 1 1 1 3 4 2 1 1 3 3 10 1 1 3 3 0 1 2 3 2 0 1 1 3 2 0 1 1 3 4 2 1 2 2 2 0 1 2 2 0 1 4 4 8 1 1 2 3 2 0 1 2
output:
63 4553 16 3465 66 4347 366 315 35 35 4347 15 15 11384 35
result:
ok 15 numbers
Test #3:
score: 5
Accepted
time: 5ms
memory: 4888kb
input:
3 15 25363 0 10 1 2 2 4 5 6 5 7 5 7 7 8 13 11 13 12 17 14 19 20 20 22 23 24 22 26 26 24 28 28 30 32 32 30 34 33 35 34 38 37 41 41 40 40 42 46 45 44 47 49 51 49 51 54 54 56 55 58 57 59 60 62 60 61 64 65 63 65 68 66 70 68 69 74 75 72 76 77 78 77 77 78 79 84 83 83 85 87 89 90 91 90 90 91 93 93 97 95 98...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok 15 numbers
Test #4:
score: 5
Accepted
time: 0ms
memory: 3576kb
input:
4 15 95 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 81 1 0 1 1 3 3 2 4 4 4 7 8 8 11 11 12 15 16 17 18 19 17 19 22 20 22 24 25 27 24 25 26 28 29 32 33 32...
output:
189 161 157 183 179 179 185 165 161 179 191 159 199 177 195
result:
ok 15 numbers
Test #5:
score: 5
Accepted
time: 4ms
memory: 4612kb
input:
5 15 24238 1 9 1 2 2 3 2 3 7 6 6 8 11 8 13 14 14 13 14 15 15 20 17 21 19 24 25 22 23 28 27 29 28 31 32 34 35 32 35 35 39 37 38 42 39 41 43 42 47 47 45 48 49 52 50 52 51 55 53 57 58 58 60 58 60 64 62 66 66 65 65 69 68 68 73 71 72 73 75 78 77 76 78 82 81 84 82 85 84 87 86 89 90 90 90 90 91 93 94 94 98...
output:
48475 54131 56879 54501 49951 55359 46639 52775 56387 53417 55987 58213 48849 46865 56865
result:
ok 15 numbers
Test #6:
score: 5
Accepted
time: 0ms
memory: 3648kb
input:
6 15 90 2 0 1 1 3 3 4 6 3 5 6 1 4 8 6 3 7 2 8 17 12 1 15 8 10 17 4 7 22 1 16 15 13 17 6 24 18 20 29 24 5 37 26 19 1 36 10 11 1 32 12 29 25 36 43 25 36 35 27 30 48 13 57 43 3 48 20 49 10 42 33 32 15 67 3 72 18 59 45 65 22 47 21 76 44 36 70 31 40 36 75 97 2 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
32399 37731 39999 28223 29668 37731 36193 26895 35436 39301 33946 31771 30975 24335 36958
result:
ok 15 numbers
Test #7:
score: 5
Accepted
time: 2ms
memory: 4640kb
input:
7 15 23937 2 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 ...
output:
291919861 146761194 947431229 721917569 513436690 452531920 95169750 435600974 157568937 921186289 544059002 432348666 320565654 309379121 377927681
result:
ok 15 numbers
Test #8:
score: 5
Accepted
time: 0ms
memory: 3928kb
input:
8 15 1 89 0 1 88 0 1 86 0 1 81 0 1 89 0 1 88 0 1 85 0 1 88 0 1 99 0 1 93 0 1 94 0 1 79 0 1 97 0 1 88 0 1 96 0
output:
643555007 320020087 809556406 776533926 643555007 320020087 414090976 320020087 356146221 792287148 157695640 15616881 389622706 320020087 654868516
result:
ok 15 numbers
Test #9:
score: 5
Accepted
time: 1ms
memory: 3928kb
input:
9 15 1 85 0 1 86 0 1 90 0 1 87 0 1 87 0 1 91 0 1 81 0 1 79 0 1 86 0 1 80 0 1 81 0 1 88 0 1 98 0 1 89 0 1 78 0
output:
414090976 809556406 196345448 53257258 53257258 538525843 776533926 15616881 809556406 483084065 776533926 320020087 976427145 643555007 299462530
result:
ok 15 numbers
Test #10:
score: 5
Accepted
time: 0ms
memory: 15532kb
input:
10 15 1 2600 0 1 2562 0 1 2885 0 1 2926 0 1 2980 0 1 2796 0 1 2809 0 1 2441 0 1 2964 0 1 2384 0 1 2634 0 1 2284 0 1 2732 0 1 2525 0 1 2635 0
output:
980378455 337526154 558193103 125913045 124855760 503883918 199525532 902720193 515375300 777422724 363348923 334557029 939566213 938891504 485461889
result:
ok 15 numbers
Test #11:
score: 5
Accepted
time: 11ms
memory: 4428kb
input:
11 15 1 97 8 1 98 8 1 75 9 1 86 10 1 91 10 1 80 10 1 99 10 1 75 10 1 81 3 1 86 8 1 76 10 1 79 9 1 77 9 1 79 8 1 92 10
output:
201967493 593344966 454636651 58812991 509364979 455029717 399412420 697505560 426878348 397782687 146643903 719871243 754719823 132594531 954628592
result:
ok 15 numbers
Test #12:
score: 5
Accepted
time: 249ms
memory: 28160kb
input:
12 15 1 2419 9 1 3000 8 1 2952 9 1 2911 10 1 2596 8 1 2997 10 1 2479 10 1 2447 10 1 2504 8 1 2325 9 1 2473 10 1 2674 8 1 2817 9 1 2303 8 1 2253 6
output:
897921773 493618043 502033461 163722526 998027298 171201566 988250983 759578319 522233752 644875547 630714473 82369707 754521000 259048908 717777794
result:
ok 15 numbers
Test #13:
score: 5
Accepted
time: 1ms
memory: 4020kb
input:
13 15 96 77 0 1 1 2 2 3 3 4 4 5 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 8 8 65 17 9 33 83 76 52 42 17 56 39 82 26 53 89 96 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ...
output:
875522633 817514869 984115449 171618725 413906221 67403237 626927815 102038917 731937401 81736574 147698013 5718686 570093465 291610 736092684
result:
ok 15 numbers
Test #14:
score: 5
Accepted
time: 1ms
memory: 4024kb
input:
14 15 79 92 0 1 2 1 3 2 5 6 6 6 10 7 8 10 13 14 13 15 16 17 18 17 18 21 24 25 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 18 33 33 18 9 48 19 2 6 12 28 3 22 50 5 24 14 10 15 42 11 44 36 38 58 21 9 96 81 0 1 2 3 4 3 2 4 7 7 1 7 10 12 13 1 9 14 6 13 18 4 2 4 14 25 3 3...
output:
69626057 106800079 696160675 125365500 105229737 980457872 857341479 727730150 931017912 72350415 700427628 857341479 458562426 105229737 33015237
result:
ok 15 numbers
Test #15:
score: 5
Accepted
time: 0ms
memory: 16432kb
input:
15 15 27219 2720 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
512213075 634563835 412223891 885815756 909933373 460122433 143582817 318866407 952581018 559698410 15451972 798343658 240180291 40997907 507956430
result:
ok 15 numbers
Test #16:
score: 5
Accepted
time: 4ms
memory: 16232kb
input:
16 15 23470 2270 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
613353516 498696894 341174230 524070747 458732519 657246209 497631698 460156266 650070681 438365748 579953962 638226266 303839474 655729798 51100917
result:
ok 15 numbers
Test #17:
score: 5
Accepted
time: 6ms
memory: 4408kb
input:
17 15 94 82 9 1 2 2 3 3 6 6 8 6 10 7 10 13 10 14 14 16 17 18 17 20 18 23 24 22 26 25 27 25 26 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 59 39 56 52 21 51 66 59 33 68 29 34 62 47 59 76 54 72 40 40 3 4 63 33 44 73 59 18 19 70 25 77 93 86 8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
57879436 325557854 91787824 410242939 853965973 142189519 742252318 181854803 57653454 102825828 223733805 982035357 963632678 929397289 890046592
result:
ok 15 numbers
Test #18:
score: 5
Accepted
time: 4ms
memory: 4416kb
input:
18 15 78 96 1 1 1 2 2 3 3 4 4 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 7 7 52 54 22 16 21 56 64 32 42 64 52 49 19 87 86 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
76805686 353383610 224346320 111078253 766068511 881559887 431130327 846136820 658010636 340111764 612573560 824188027 435154505 227628660 45266228
result:
ok 15 numbers
Test #19:
score: 5
Accepted
time: 252ms
memory: 29264kb
input:
19 15 26104 2591 3 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
352998989 343378163 332642314 329512384 132607327 87163047 200914906 690708263 643035325 490644560 544357196 370133318 274907996 878486015 823925934
result:
ok 15 numbers
Test #20:
score: 5
Accepted
time: 285ms
memory: 28984kb
input:
20 15 22821 2558 8 1 1 1 3 2 4 2 5 5 5 7 7 13 4 15 12 1 17 15 6 10 10 13 20 20 1 16 14 9 9 28 24 14 28 2 28 35 20 30 37 1 9 21 35 42 23 41 11 15 29 10 1 13 6 24 11 11 46 32 39 32 10 59 57 20 24 51 24 60 28 65 16 31 42 25 12 27 28 53 49 15 12 58 73 83 47 7 71 2 2 26 57 82 61 17 17 48 96 23 83 2 41 59...
output:
852082753 663863799 567411082 526354875 894631436 262990076 719766589 173209722 880032338 29895723 506677794 954758703 758235022 133292061 393482362
result:
ok 15 numbers
Extra Test:
score: 0
Extra Test Passed