QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #747007 | #4222. 题 | propane | 100 ✓ | 866ms | 57592kb | C++20 | 2.5kb | 2024-11-14 16:08:51 | 2024-11-14 16:08:51 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<unordered_map>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
vector<int> pos[19 * 3 + 1];
LL q[657800];
int p[657800][7];
int l[8];
LL pow20[8];
int g[8][4];
int dp[657800];
unordered_map<LL, int> mp;
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
// 132
// 213
// 321
pow20[0] = 1;
for(int i = 1; i < 8; i++) pow20[i] = pow20[i - 1] * 20;
l[0] = 0;
l[1] = l[2] = l[3] = 1;
l[4] = l[5] = l[6] = 2;
l[7] = 3;
memset(g, -1, sizeof g);
g[0][1] = 1;
g[1][3] = 4;
g[4][2] = 7;
g[0][2] = 2;
g[2][1] = 5;
g[5][3] = 7;
g[0][3] = 3;
g[3][2] = 6;
g[6][1] = 7;
int T;
cin >> T;
while(T--){
int n; string s;
cin >> n >> s;
for(int i = 0; i <= 3 * n; i++) pos[i].clear();
mp.clear();
mp.reserve(657800);
int c[7]{}; int tot = 0;
auto dfs = [&](auto &&dfs, int u, int len, int cnt, LL val) -> void {
if (u == 7){
len += (n - cnt) * 3;
pos[len].push_back(tot);
memcpy(p[tot], c, sizeof c);
mp[val] = tot;
q[tot] = val;
dp[tot] = 0;
tot += 1;
return;
}
for(int i = 0; cnt + i <= n; i++){
c[u] = i;
dfs(dfs, u + 1, len + l[u] * i, cnt + i, val + pow20[u] * i);
}
};
dfs(dfs, 0, 0, 0, 0);
dp[pos[0][0]] = 1;
for(int i = 0; i < 3 * n; i++){
int l = 1, r = 3;
if (s[i] != '0') l = r = s[i] - '0';
for(auto x : pos[i]){
for(int j = 0; j < 7; j++){
if (p[x][j] != 0){
for(int k = l; k <= r; k++){
if (g[j][k] != -1){
LL nval = q[x] - pow20[j];
if (g[j][k] != 7) nval += pow20[g[j][k]];
int nxt = mp[nval];
dp[nxt] = (dp[nxt] + 1LL * dp[x] * p[x][j]) % mod;
}
}
}
}
}
}
cout << dp[pos[3 * n][0]] << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 3ms
memory: 12280kb
input:
5 1 123 1 100 1 000 1 300 1 010
output:
0 1 3 1 1
result:
ok 5 lines
Test #2:
score: 10
Accepted
time: 0ms
memory: 12324kb
input:
5 1 303 2 000320 2 002000 2 002020 2 020020
output:
0 36 60 12 12
result:
ok 5 lines
Test #3:
score: 10
Accepted
time: 3ms
memory: 12312kb
input:
5 2 110133 3 200010000 3 002002200 3 300000000 3 000000130
output:
0 5940 540 15120 7560
result:
ok 5 lines
Test #4:
score: 10
Accepted
time: 0ms
memory: 12332kb
input:
5 5 000000000000000 4 000000000000 3 000000000 2 000000 1 000
output:
864823720 29937600 45360 180 3
result:
ok 5 lines
Test #5:
score: 10
Accepted
time: 4ms
memory: 12672kb
input:
5 6 000121310223223210 7 033221120002010100230 7 000003020000010302010 7 000010002020302300100 7 030100002033300000000
output:
26853120 152413083 939384999 4309685 970165754
result:
ok 5 lines
Test #6:
score: 10
Accepted
time: 7ms
memory: 13188kb
input:
5 9 120332011311030220200103301 10 200003200103011232000202201120 10 000000201330030030101000003000 10 020000002032000000200000100002 10 100200322001000000320000002010
output:
963757075 290911546 487693965 730680478 984422198
result:
ok 5 lines
Test #7:
score: 10
Accepted
time: 29ms
memory: 21660kb
input:
5 13 000000000000000000000000000000000000000 12 000000000000000000000000000000000000 11 000000000000000000000000000000000 10 000000000000000000000000000000 9 000000000000000000000000000
output:
856865849 574346463 607449787 883895867 88660419
result:
ok 5 lines
Test #8:
score: 10
Accepted
time: 198ms
memory: 32552kb
input:
5 15 331110203302222220331213331310312220103030021 16 001301022200100032010330002213000300220033210033 16 020002030002000330003200030010000000000100002300 16 320000001003222000003000003000300010323113200020 16 000203000000000000010100000000000000002000210000
output:
70336694 482512438 740138646 212387388 427674884
result:
ok 5 lines
Test #9:
score: 10
Accepted
time: 551ms
memory: 45912kb
input:
5 17 221001103220113003322101120223031133120301212031002 18 201000020000000010323100000333030002012000213100030001 18 013203020100001021200030003102000130000002330303302120 18 010003030200000200100000002000000000000302000203103300 18 000001000132020000200321023010000000000000000132210300
output:
821788453 589132243 303959134 648206569 571580782
result:
ok 5 lines
Test #10:
score: 10
Accepted
time: 866ms
memory: 57592kb
input:
5 18 331110100201233220121012022130200011112133012123201012 19 221011310310012302220013020123002132313030023020101110230 19 202000300003001300011000011021320001000300320020302022103 19 010030200000000000300300310000001302002000010230000330020 19 000000000000031000000000131200020001000020000001020000...
output:
171958822 242716134 229925968 914555153 59496792
result:
ok 5 lines
Extra Test:
score: 0
Extra Test Passed