QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #413868 | #8330. Count off 3 | ucup-team173 | AC ✓ | 370ms | 71064kb | C++23 | 6.4kb | 2024-05-18 10:49:48 | 2024-05-18 10:49:48 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int Mod = 1e9 + 7;
int f[5005][7][7][7][2];
int sum[5005][8][7][7][7];
int Fpow[10005][4];
void add(int &x, int y) {
x += y, x >= Mod ? x -= Mod : 0;
}
void init() {
Fpow[0][1] = Fpow[0][2] = Fpow[0][3] = 1;
for (int i = 1; i <= 10000; i++) {
Fpow[i][1] = Fpow[i - 1][1];
Fpow[i][2] = Fpow[i - 1][2] * 2 % 7;
Fpow[i][3] = Fpow[i - 1][3] * 3 % 7;
}
f[0][0][0][0][0] = f[0][0][0][0][1] = 1;
for (int p = 0; p <= 5000; p++) {
if (p) {
for (int t = 0; t < 7; t++) {
for (int tt = 0; tt < 7; tt++) {
for (int ttt = 0; ttt < 7; ttt++) {
int a = (t + Fpow[(p - 1) << 1][1]) % 7;
int b = (tt + Fpow[(p - 1) << 1][2]) % 7;
int c = (ttt + Fpow[(p - 1) << 1][3]) % 7;
if (p != 1) add(f[p][t][tt][ttt][0], f[p - 1][t][tt][ttt][0]);
add(f[p][a][b][c][0], f[p - 1][t][tt][ttt][0]);
a = (t + Fpow[(p << 1) - 1][1]) % 7;
b = (tt + Fpow[(p << 1) - 1][2]) % 7;
c = (ttt + Fpow[(p << 1) - 1][3]) % 7;
add(f[p][t][tt][ttt][1], f[p - 1][t][tt][ttt][1]);
add(f[p][a][b][c][1], f[p - 1][t][tt][ttt][1]);
}
}
}
}
for (int sta = 0; sta < 8; sta++) {
for (int t = 0; t < 7; t++) {
for (int tt = 0; tt < 7; tt++) {
for (int ttt = 0; ttt < 7; ttt++) {
sum[p][sta][t][tt][ttt] = f[p][t][tt][ttt][1];
}
}
}
if (sta & 4) {
for (int t = 1; t < 7; t++) {
for (int tt = 0; tt < 7; tt++) {
for (int ttt = 0; ttt < 7; ttt++) {
add(sum[p][sta][t][tt][ttt], sum[p][sta][t - 1][tt][ttt]);
}
}
}
}
if (sta & 2) {
for (int t = 0; t < 7; t++) {
for (int tt = 1; tt < 7; tt++) {
for (int ttt = 0; ttt < 7; ttt++) {
add(sum[p][sta][t][tt][ttt], sum[p][sta][t][tt - 1][ttt]);
}
}
}
}
if (sta & 1) {
for (int t = 0; t < 7; t++) {
for (int tt = 0; tt < 7; tt++) {
for (int ttt = 1; ttt < 7; ttt++) {
add(sum[p][sta][t][tt][ttt], sum[p][sta][t][tt][ttt - 1]);
}
}
}
}
}
}
// cerr << (db) clock() / CLOCKS_PER_SEC << '\n';
}
vector<int> lim[3];
int now[3];
int calc(int len, vector<vector<int>> val) {
int ans = 0;
int Sum[4][4][4];
memset(Sum, 0, sizeof(Sum));
for (int t = 0; t < 7; t++) {
for (int tt = 0; tt < 7; tt++) {
for (int ttt = 0; ttt < 7; ttt++) {
int s;
if (s = f[(len + 1) >> 1][t][tt][ttt][0]) {
int a = (t + val[0][0]) % 7;
int b = (tt + val[1][0]) % 7;
int c = (ttt + val[2][0]) % 7;
add(Sum[min(a, 7 - a)][min(b, 7 - b)][min(c, 7 - c)], s);
}
}
}
}
for (int t = 0; t < 4; t++) {
for (int tt = 0; tt < 4; tt++) {
for (int ttt = 0; ttt < 4; ttt++) if (Sum[t][tt][ttt]){
now[0] = t, now[1] = tt, now[2] = ttt;
for (int p = 0; p < 3; p++) {
int g = (now[p] + 7 - val[p][1]) % 7;
int h = (7- (now[p] + val[p][1]) % 7) % 7;
lim[p].clear();
lim[p].push_back(-1);
lim[p].push_back(g);
if (g != h) {
lim[p].push_back(h);
}
}
ll res = 0;
for (auto a : lim[0]) {
for (auto b : lim[1]) {
for (auto c : lim[2]) {
int sta = ((a == -1) << 2) | ((b == -1) << 1) | (c == -1);
int p = (a != -1) ^ (b != -1) ^ (c != -1);
if (p) res -= sum[len >> 1][sta][(a + 7) % 7][(b + 7) % 7][(c + 7) % 7];
else res += sum[len >> 1][sta][(a + 7) % 7][(b + 7) % 7][(c + 7) % 7];
}
}
}
res = (res % Mod + Mod) % Mod;
if (res) {
ans = (ans + 1ll * res * Sum[t][tt][ttt]) % Mod;
}
}
}
}
return ans;
}
bool check(vector<vector<int>> val) {
for (int i = 0; i < 3; i++) {
if (val[i][0] == val[i][1]) {
return 0;
}
if ((val[i][0] + val[i][1]) % 7 == 0) {
return 0;
}
}
return 1;
}
void solve() {
string s;
cin >> s;
int len = s.size();
vector<vector<int>> val(3, vector<int>(2));
int ans = 0;
for (int i = 0; i < len; i++) {
if (s[i] == '1') {
if (i != len - 1) {
add(ans, calc(len - i - 1, val));
}
for (int t = 0; t < 3; t++) {
val[t][(len - i - 1) & 1] = (val[t][(len - i - 1) & 1] + Fpow[len - i - 1][t + 1]) % 7;
}
if (i == len - 1) {
if (check(val)) {
add(ans, 1);
}
}
}
}
cout << ans << '\n';
// cerr << (db) clock() / CLOCKS_PER_SEC << '\n';
}
int main() {
// freopen("C.in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
init();
int t = 1;
cin >> t;
while (t--) solve();
// cerr << (db) clock() / CLOCKS_PER_SEC;
return 0;
}
/*
5
1
1010
110101
1000111000
101101001000
*/
这程序好像有点Bug，我给组数据试试？
详细
Test #1:
score: 100
Accepted
time: 41ms
memory: 70792kb
input:
5 1 1010 110101 1000111000 101101001000
output:
1 2 15 114 514
result:
ok 5 number(s): "1 2 15 114 514"
Test #2:
score: 0
Accepted
time: 45ms
memory: 70736kb
input:
10 1 11 1000 10111011 1000110100101001 11101110000001000011010011011000 110011000111110001101010101100100011010010101000011111001101011 11010111011101000010101111011111011011100001001101010011101011111111011011111101110110010011001101000001000111100010010111000010 10000000000000000000000000000000000...
output:
1 1 2 45 6591 814196699 193088128 849103726 497125329 363076920
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 141ms
memory: 71044kb
input:
10 1 101 100101000 111111001111011001111100111 100001101010101000101110010111010010001101101110011111000001010001111100101010000 111001010100100100110011110111000111001001001001000100000011000110011000110101010010100000100101110101000011000011100010011001011000101110100111000110011011010111011111011...
output:
1 2 64 27062688 486363229 184013394 580592021 118930214 772664718 344619804
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 200ms
memory: 70856kb
input:
10 1 1011 1101001010001110 1000010101110010000010010000000000001010111001001001110011001101 1001100101110111001000100100110111110001110010111011010101010111011101111101111100010000001100001001011100111100010110011010000010000000001100111011000001110011010000100000110101010011111100010111111100011011...
output:
1 3 10053 860833891 537931408 329471109 368911735 157523156 595487313 534701861
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 251ms
memory: 70824kb
input:
10 1 11111 1010110010010000111001001 10011010100100001000110000111101101000111100001000000101010001100111111010001000101000000011100101000101100111100001001101100 11000100100010011101010101001011100010001100001010110011110101001101011000110001000111101010010000110111010001100100100111001000001000010...
output:
1 10 4692555 763463648 464152115 115362567 880780461 578723006 560068977 423846910
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 279ms
memory: 70816kb
input:
10 1 101011 100100110100111100001101000101011100 1011011000011001101101010110000111011001001100110101111100110000100100101010000000110110010001110011101011000001011001000010001011101110110100110010111111000101101010110000101010101011001111100111011001101111011101 101000000111000010111000110000011000...
output:
1 13 955673880 266148454 368723690 496979115 190983211 772121423 932555320 843716403
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 286ms
memory: 70848kb
input:
10 1 1101101 1100111111001000111100000010000111000000010101001 110111101101011000111101100110010011011100101110101111110011001111001101001000011001110011110101001110010110011110011001111010010101010011010011101101111010111000001110110111011011101000100001000001101110010111100110001110011101110111100...
output:
1 29 912933242 912560788 607401363 477602366 394403189 275067439 592568023 75193370
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 306ms
memory: 70720kb
input:
10 1 10000010 100101110110100111100000100011111111010001100010100001100110001 111111000010011010111011111110000010101101011110100001101011110000001111001110001111110101000000010000001011000101101011010111011101111110101001000110011101010000111001011111100100010000010110110101010001110100111110110001...
output:
1 32 959140870 614330473 849221876 787816311 359958989 239371459 534701861 254356877
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 313ms
memory: 71056kb
input:
10 1 111110011 111101001101011110100011110000100110011101010111111110100001111001101000100101101 11011010000110101011111110110011101010100100110001001111111011010000101111110001001011000011010101001000101110000100011011100101010110010101000101010111101100101110111100011011011000101101001001001100111...
output:
1 99 286317277 694681686 723919544 789291149 680541846 694957099 453387561 757810824
result:
ok 10 numbers
Test #10:
score: 0
Accepted
time: 331ms
memory: 70992kb
input:
10 1 1001001110 10110010111110100100111100111101101010111110111011001110000111101011011010110011110000000001110100 11000101011111110110100101100100100000010110001011100010101111111000000111000101100110111110101010111110010110111111110010110010001100000000111000101100010001110010001011111110101011111...
output:
1 120 987933828 449323095 435643580 557750562 122442298 758115947 388795572 87146822
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 329ms
memory: 71064kb
input:
10 1 11010010100 100110110000100111011101001111000000000110111100011110111011110100001010101000000000100000101100100101110101011100111000 110111100000010010111000111011111100010100100111101001001101111010011011100100001010100010100011110111111100101011100111111011011000000111001111000101111010110111...
output:
1 325 391030697 323231960 401473132 822267612 841573845 283856764 804647498 76347459
result:
ok 10 numbers
Test #12:
score: 0
Accepted
time: 331ms
memory: 70768kb
input:
10 1 111111110011 100111010001010010111100011101110011110100101101010111001110101111000111010001111110000001000011010111010001001000011101100011100010010100010000 11001011101100010011111001010110110000110110011001011001000001001110010100100000000101100010001011010010001101000101110000111100100000001...
output:
1 704 677678115 593427859 667002509 574438492 664907465 979953874 8529137 613727900
result:
ok 10 numbers
Test #13:
score: 0
Accepted
time: 340ms
memory: 71020kb
input:
10 1 1100110101011 100111000010011100111101101100110010110000100011110101100100011001101011100011101101110111001101000001110010111001110011100101000111111000010101101100011000010100010101 1111010000010011010010011000010000000001000110111011101100111011100010110011100110011110011011110011110100011001...
output:
1 1146 832402516 402106502 689225542 416112434 991952024 938688647 880733772 630306115
result:
ok 10 numbers
Test #14:
score: 0
Accepted
time: 344ms
memory: 70852kb
input:
10 1 11000000000111 110010000100100011111101001100111010110111011101101011001001010110101111111101001000000100110011110101100111010110100100010100000100000011100010101011010001100001000111000101000011010110010100000 101001000110100011110100011001010101001010011111010111111001100111111100101111110111...
output:
1 2087 659256442 942088668 754989716 908871865 566839365 111034927 696022638 206335876
result:
ok 10 numbers
Test #15:
score: 0
Accepted
time: 350ms
memory: 70844kb
input:
10 1 111100001011110 101100010011110001000011110010011010011100110010111110100111111111100101100111010101001101111001111010111011011111000111000101101010001100111010100110110000111110100100101000001101111100000101101100010110101000011001110001101 11111110001100110111110110100010111010100010010010010...
output:
1 5612 120730460 903512843 440620378 736669452 35297346 414402862 87146822 461180872
result:
ok 10 numbers
Test #16:
score: 0
Accepted
time: 338ms
memory: 70764kb
input:
10 1 1011110111101110 11111011001101100000000011011111011000101001100010000000001010011110010000100000111100101011101111111111001000110011110000011001000111000010101100001001100111100100000010101101111100100100101110101100000000011101011100010111111010000101011000110010011000 11110011001110110000001...
output:
1 9074 47298040 806126372 607928251 829797230 861514498 6535505 135611721 148853296
result:
ok 10 numbers
Test #17:
score: 0
Accepted
time: 340ms
memory: 70852kb
input:
10 1 11101111010010001 1111011100010101011101000110010001011001010101000100111100010110101010010001100101001001011111101001101100110100100100101101011001100000101011000100001011101000101000110000110100100100001001000011000111000010100011001111111011010001110111101111010011100010110001010010000100001...
output:
1 25268 485539600 497476229 129697011 91489334 354698980 228961474 875061949 618786188
result:
ok 10 numbers
Test #18:
score: 0
Accepted
time: 359ms
memory: 70788kb
input:
10 1 101101011100110001 100111001100000111101000101110011011011011111101011110101111000010000101010001010110100101001001100010101100101001110110001101101100111111100001000100010010110101110010111101100110010000010001101011001110001001100111101100111010100100000000000010000100101001000110000111100100...
output:
1 38342 769759919 33866310 945890505 127750526 125262837 888967227 757810824 441419016
result:
ok 10 numbers
Test #19:
score: 0
Accepted
time: 359ms
memory: 71060kb
input:
10 1 1001100011010110111 11100110010001111111110100011111100100011011110000110100000111101100111110111010111010111001111111100111011000000101001111000010001100010001111001011000111111001111100100101101011001110011100000111011111110101000111011101101110101101101110101100000011000001001011011100001111...
output:
1 65218 438898572 348219276 776140964 704823526 170625715 198310775 477853700 897436999
result:
ok 10 numbers
Test #20:
score: 0
Accepted
time: 370ms
memory: 70772kb
input:
10 1 11010100111111001011 1000011001001001110110101001100001001101001001010010101010001110011001001000000000110001100110001110110111010100101011011001100101001110111001101101000111101100010110101100101110111101000101111010100110001011110111000110000110110111011101110010010011010001110101010110010000...
output:
1 183823 238142747 846693477 959968477 260267123 642987070 779134130 951392182 679687101
result:
ok 10 numbers
Extra Test:
score: 0
Extra Test Passed