QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648020#5407. 基础图论练习题ddxrS20 95ms4712kbC++141.7kb2024-10-17 16:37:102024-10-17 16:38:40

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 16:38:40]
  • 评测
  • 测评结果:20
  • 用时:95ms
  • 内存:4712kb
  • [2024-10-17 16:37:10]
  • 提交

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%