QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#648020 | #5407. 基础图论练习题 | ddxrS | 20 | 95ms | 4712kb | C++14 | 1.7kb | 2024-10-17 16:37:10 | 2024-10-17 16:38:40 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
const int N = 5e3 + 5;
int n;
char s[N];
bool vis[N][N];
vector<int> E[N];
int low[N], dfn[N], col[N], tcnt, cnt;
stack<int> stk;
ll qpow(ll a, ll b) {ll ans = 1; while(b) {if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1;} return ans;}
int turn(char x) {return (x >= '0' && x <= '9' ? (x ^ 48) : (10 + (x - 'A')));}
void tarjan(int u, int fa) {
low[u] = dfn[u] = ++tcnt, stk.push(u);
for(int v : E[u]) if(!vis[u][v]) {
if(!dfn[v]) tarjan(v, u), low[u] = min(low[u], low[v]);
else if (!col[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {cnt++; int dx; do{dx = stk.top(), stk.pop(); col[dx] = cnt;} while (dx != u);}
}
void solve() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) E[i].clear();
for(int i = 2, l; i <= n; i++) { l = (i - 1) / 4 + 1;
cin>>(s + 1);
for(int j = 1; j <= l; j++) for(int k = 4 * j - 3, x = turn(s[j]); k <= 4 * j && k < i; k++, x >>= 1) (!(x & 1) ? E[k].push_back(i) : E[i].push_back(k));
}
ll ans = 0;
for(int i = 1; i <= n; i++) for(int j : E[i]) {
tcnt = cnt = 0;
for(int k = 1; k <= n; k++) dfn[k] = col[k] = 0;
while(!stk.empty()) stk.pop();
vis[i][j] = true, E[j].push_back(i);
for(int k = 1; k <= n; k++) if(!dfn[k]) tarjan(k, k);
if(i <= j) ans = (ans + qpow(2, 1ll * (j - 2) * (j - 1) / 2 + i - 1) * cnt % mod) % mod;
else ans = (ans + qpow(2, 1ll * (i - 2) * (i - 1) / 2 + j - 1) * cnt % mod) % mod;
vis[i][j] = false, E[j].pop_back();
}
printf("%lld\n", ans);
}
int main() {
int t; cin>>t;
while(t--) solve();
return 0;
}
详细
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 85ms
memory: 4440kb
input:
10000 100 1 2 2 8 C0 F0 27 78 AE1 C01 511 D87 EF20 3873 2742 73D0 DC9B0 FB2A3 9C011 9B4E0 95DC00 A7B980 F43531 6A6245 5347BE0 1A6C8A1 88E46D6 64CF3AE D25F63C1 C894E4C3 1C0AFD73 EC1C3F9A 087CE17C0 22149A380 B28038AF1 B9CA21C7F D78F5307C1 49045489A2 72C4DE6FD1 7713F40D05 EEE8878EEC1 310E62812B1 DA9D5B...
output:
281603732 13 285212672 371842543 84 0 1983 2 268505087 268435455 719476515 32785 2 719476771 123 2621567 2523 0 719476275 371842543 2097159 41087 34815 3113984 719478307 502774846 719476267 719476259 719476259 65224 268697613 719477283 36863 2171007 719476259 371842543 120 84 219 5769215 268435455 1...
result:
ok 10000 numbers
Test #2:
score: 20
Accepted
time: 95ms
memory: 4712kb
input:
10000 100 0 2 1 8 41 F2 30 30 F60 7D2 605 024 E910 45F3 3CB0 3B88 0FE21 A7DF3 3B162 70D7A 70B9C1 DFB731 883B33 930FC6 4F8BEC1 CC73551 1A344F3 88966C9 3879FE20 93839630 B6C3FF85 F6D5F7B1 F757DCB20 63C3512A3 9BFD99935 ED1E4F248 ECAB4DA041 EA5CE54511 EA07C72263 F8ADE1FD8C B220226E1F0 34F274277A0 4A1A14...
output:
281603732 2097151 0 144 268443647 32767 2097151 2 19 903009902 0 268435455 1103 1099 268501119 719476259 17 574715508 0 268435455 321515202 1023 745417303 84 2097151 371842543 301989887 272629791 268435455 153406 0 719476531 2 3368 132695 0 402653183 268435455 371842543 0 0 17 719476259 371842543 23...
result:
ok 10000 numbers
Test #3:
score: 20
Accepted
time: 94ms
memory: 4440kb
input:
10000 100 1 0 3 7 11 C1 71 1A C01 E43 237 9B5 33C1 0DE3 7C74 B042 38E60 65480 1D103 862A7 B2DA80 C63273 CF8AD3 AFBDC2 2816D11 1B12351 1869CC5 6BC6DB3 50E5FAB1 4E291CB2 4DF82716 0D410C3E FD4B31250 8BF2C54A0 1266235D1 757755C58 724DFD1960 F6D1285122 281CDE0BB1 5EF924A6A9 786A08B90C1 BE8C674EE52 B9EFA2...
output:
281603732 371842549 371842543 268435459 1281 371842543 719476259 371842543 84 60934 108 2 268435455 108 1159 108 2097663 2 371842543 719476259 2 371842543 1536 7288681 269746175 371842543 268435463 2 371842543 0 899345324 84 1183 0 19 93 371842543 21 21 21 1152 371842543 780828798 268435455 71947625...
result:
ok 10000 numbers
Test #4:
score: 20
Accepted
time: 86ms
memory: 4436kb
input:
10000 100 0 0 1 3 D1 D0 B4 DD 940 C13 2C3 62A E900 2FC1 2470 E6EE 80151 912A3 CADA5 7F6D3 0CB410 E17771 686F85 68DFEE FABD991 150D7A2 90C8247 5B06F87 46894CE0 42575142 BC2873D5 8F1E0A9C D26EDC921 30F8DCAA2 6ECD63697 C739CFD42 631139F800 A57ED99C72 20B0B17882 347727E7CA E619F1E8A91 1DC6F46E610 01C38C...
output:
281603732 21 371842543 2 102 102 0 268435455 1536 17 719476259 2 2 371842543 2621443 32767 2 21 371842543 189 719476259 1035 1087 2097151 0 719476259 2 2 268435455 0 21 144 719476259 2 1023 32767 2097151 32775 719476259 371842543 0 36863 21 2097151 2 32767 268435455 2 32768 180 21 123 371842543 93 3...
result:
ok 10000 numbers
Test #5:
score: 20
Accepted
time: 92ms
memory: 4696kb
input:
10000 100 1 3 3 C A1 A2 96 AA 9D1 A01 C16 EDD 2560 D652 0990 0630 1CCF0 6FCD0 FF216 A1AE4 733020 7287D3 E64A46 ADA8C2 AD3E2A0 02BC872 6D92D01 05C5759 33F30180 D42829D1 42734D77 01C7FE14 047CF2770 AE654B450 8C50339E5 AABDF020C 92316BB5E0 4E2EA0A9E2 3C962A0C27 9956ED19E9 458EFDCCCC0 0B1BC934520 5B83A4...
output:
281603732 21 2359295 719476259 105 0 268435455 2113543 33023 21 2 0 0 32847 2097151 405396975 21 371842543 2162687 268435455 84 371842543 105 32767 3343 268435455 371842543 719476259 0 32895 2 719476259 21 2 21 21 21 21 21 21 21 171 2621439 268959743 2113791 108 2 32767 268435487 268435463 32840 78 ...
result:
ok 10000 numbers
Test #6:
score: 20
Accepted
time: 85ms
memory: 4396kb
input:
10000 100 1 3 0 7 D1 82 10 3D E60 EE2 0B1 5A5 10C0 B543 0AD3 1390 45750 C6830 0EAB5 B2D55 FF2090 503CC2 0BB701 EB004B 3FDD210 17A52F1 44B5255 7418726 75843761 150CEF50 F20F26E6 8FBBA768 D24A5D161 AA31E8A90 373E9FE24 D32AA0A0A F4C90F3500 6C36C6F8C3 726D14EF35 CFC549657E 10803BE30D1 4DF734243E0 FF192B...
output:
281603732 0 2375679 21 21 2097151 2098207 21 2 2097151 0 0 2 84 0 32767 268435455 2 21 2097279 1040 2 268435455 93 2097151 2097151 105 719476259 2170879 36863 268435455 371842543 268435455 719476259 719476259 102 0 371842543 2 21 1535 1025 21 371842543 2 371842543 0 371842543 21 1033 21 371842543 17...
result:
ok 10000 numbers
Subtask #2:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #7:
score: 0
Time Limit Exceeded
input:
10000 300 1 0 5 7 B1 C2 26 32 DA0 243 682 E2E D4B1 DFD3 60C3 4D66 826E1 D8511 AFC36 254F4 EC8F70 F5B480 7DEA20 06DF55 3EA08A1 C6B5463 C9B2C45 544D18E 2693C7C0 31E27182 D31059D1 BE767720 AC55C6D80 A21839A80 AE17E0DD6 772EF61A9 66EE846D51 B19BE410D0 03A8D64927 3297B9C9DC 05E209071C0 0A327E1EBE2 7C4427...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%