QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#668329 | #7717. Bitsets | ucup-team173# | AC ✓ | 1591ms | 395612kb | C++20 | 2.6kb | 2024-10-23 13:39:44 | 2024-10-23 13:39:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<string> s(n + 1);
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
if (n <= 1e4) {
vector cnt(n + 1, vector<int>(n + 1));
for (int j = 0; j < m; j++) {
int lst = n;
for (int i = n; i >= 1; i--) {
if (i == n || s[i][j] != s[i + 1][j]) {
lst = i;
}
cnt[i][lst]++;
}
}
for (int i = 1; i <= n; i++) {
for(int j = n - 1; j >= i; j--) {
cnt[i][j] += cnt[i][j + 1];
}
}
int k, x, y, z, a = 1, b = n;
cin >> k >> x >> y >> z;
ll ans = 0;
for (int i = 1; i <= k; i++) {
int l = min(a, b), r = max(a, b);
int res = cnt[l][r];
a = (1ll * a * x + 1ll * res * y + z) % n + 1;
b = (1ll * b * y + 1ll * res * z + x) % n + 1;
ans += res;
}
cout << ans << '\n';
} else {
vector<bitset<100>> val(n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
val[i][j] = s[i][j] - '0';
}
}
vector And(20, vector<bitset<100>>(n + 1));
vector Or(20, vector<bitset<100>>(n + 1));
for (int i = 1; i <= n; i++) {
And[0][i] = Or[0][i] = val[i];
}
for (int i = 1; i < 20; i++) {
for (int j = 1; j + (1 << i) - 1 <= n; j++) {
And[i][j] = And[i - 1][j] & And[i - 1][j + (1 << i - 1)];
Or[i][j] = Or[i - 1][j] | Or[i - 1][j + (1 << i - 1)];
}
}
vector<int> Lg(n + 1);
Lg[0] = -1;
for (int i = 1; i <= n; i++) Lg[i] = Lg[i >> 1] + 1;
int k, x, y, z, a = 1, b = n;
cin >> k >> x >> y >> z;
ll ans = 0;
for (int i = 1; i <= k; i++) {
int l = min(a, b), r = max(a, b), k = Lg[r - l + 1];
auto t1 = (And[k][l] & And[k][r - (1 << k) + 1]);
auto t2 = (Or[k][l] | Or[k][r - (1 << k) + 1]);
auto t3 = t1 ^ t2;
int res = m - (t3.count());
a = (1ll * a * x + 1ll * res * y + z) % n + 1;
b = (1ll * b * y + 1ll * res * z + x) % n + 1;
ans += res;
}
cout << ans << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while(t--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
input:
4 10 1010110101 0101111001 1101101101 1011010000 4 10 5 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
6 3 110 011 010 100 101 111 5 7 5 5
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
10 10 1100101001 0011100101 1100001110 0101011100 1001011010 0010101101 1001011011 0010110000 1001100111 0010101000 10 11 11 11
output:
26
result:
ok 1 number(s): "26"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
6 7 1101001 1000110 0010000 1110001 1110100 0001011 15 7 5 7
output:
30
result:
ok 1 number(s): "30"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
10 13 0101011101010 0100000011001 0001101010111 1101000111100 1001110000110 0110011000110 1101101110100 0101101110011 0000100011100 1100010110100 20 11 11 11
output:
60
result:
ok 1 number(s): "60"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
12 15 010010101101011 010000100100011 110011010100011 111011101010111 101110111010100 100000111011011 010100001101100 001011010111100 000011011100010 101100101001010 010000111101111 110100011011000 25 11 13 13
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
15 16 1111010001110110 1111100101111111 1111111111001010 0010100111111001 1011011000001000 1111000101000000 1001101100100011 0010111000001110 0011111000010001 1000011111011111 1101000111000001 0010010100001011 1110001111111010 0011100110100001 0101110010101101 30 13 13 17
output:
448
result:
ok 1 number(s): "448"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
13 15 001100110010010 011100110100111 111100000000110 111000011101010 111100011001010 100111101001001 000110010111101 100101000000100 011010001000000 101001100011100 011110111111000 010110111100111 110010010100110 35 13 13 11
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
11 9 110101001 001010011 000100101 110011000 110101110 001001100 110100110 100110000 100010111 110110000 111100000 40 13 11 13
output:
47
result:
ok 1 number(s): "47"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10 18 010111010010010001 111010101000100111 011010111100011001 000010000111001111 101010010000110100 001110000101111101 010101011011000100 111011110001010010 111010101101000000 100101010111101100 45 11 11 11
output:
353
result:
ok 1 number(s): "353"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
11 17 01100000011010100 11100001111000101 10011100111011011 10011110010011000 10110110111110010 01001001101111000 11010101101101110 01101101110001110 11101000000101001 00000110000001000 10001111001100010 50 13 11 13
output:
228
result:
ok 1 number(s): "228"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
1 1 0 1 2 2 2
output:
1
result:
ok 1 number(s): "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 10 0010001000 1 2 2 2
output:
10
result:
ok 1 number(s): "10"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
10 1 0 0 0 0 1 0 0 0 1 0 1 11 11 11
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
100 100 0001000000000000100100100100000000100100100010000000000000000000000010000000000010001000000000000000 0000000000000000000000000000000000000000000000000000000000100000010000000010001000000100001000000000 000000000000000000000000000001000000010001000000000000000000000000000000100000000000001000...
output:
709
result:
ok 1 number(s): "709"
Test #16:
score: 0
Accepted
time: 2ms
memory: 4360kb
input:
500 500 1011111111111111111111111111011111110111111101111111111111111111111101111111111111111111111111111111011111111111111101111110101111111111111111101111111111111101110101111111110111111101111111111110111100111111101111111101011111111111111111111111111111111111111011111101111111111111111111111111...
output:
1394
result:
ok 1 number(s): "1394"
Test #17:
score: 0
Accepted
time: 6ms
memory: 8240kb
input:
1000 1000 00000000000000000000000000010000001110000000001000000100000000000000000000000000000000000001000000001000000000000000000000000000000000100010000000000000000000000000000000100000100100100100000000000000000000000000001100000000000001100000000000000000000000000000010000100000000000010000000000...
output:
21974
result:
ok 1 number(s): "21974"
Test #18:
score: 0
Accepted
time: 72ms
memory: 395612kb
input:
10000 100 1110111111110111111111111111111111011111111111011111111011111111111011111111111111111101111111111111 1110111101111111111111111111111111111111110111111111111111111111011111111101111111111111111111111111 1111110111111111111111111111011111111111111111111111111111111111111111111101111111111111...
output:
3586
result:
ok 1 number(s): "3586"
Test #19:
score: 0
Accepted
time: 8ms
memory: 4480kb
input:
100 10000 00110000010011110000100010110001110000001000010010110100001100010000011100100001111000000010000001000100101001000000010101001100000010100011011001000101001110000100100100100110000111010100000000101000001100011001101101011000010001110110000010010000000000000011101101100010110010100111000011...
output:
1046213
result:
ok 1 number(s): "1046213"
Test #20:
score: 0
Accepted
time: 27ms
memory: 102340kb
input:
5000 200 11000000100100000000000010001000000000000000000000000000010000000000000000000001000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000000100000000000000000000000000010000000000000000000000010000000100000000000100000001000...
output:
170424
result:
ok 1 number(s): "170424"
Test #21:
score: 0
Accepted
time: 47ms
memory: 102340kb
input:
5000 200 00000000000000000000000000000000000000000000000000000000000000000000000000000000100000001000000000000000000000010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000 000100000000000000001000010000000000000000000100000001000000000001000000000100000000000010...
output:
2499626
result:
ok 1 number(s): "2499626"
Test #22:
score: 0
Accepted
time: 294ms
memory: 102352kb
input:
5000 200 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000010000100000000000 000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000...
output:
35029587
result:
ok 1 number(s): "35029587"
Test #23:
score: 0
Accepted
time: 263ms
memory: 102372kb
input:
5000 200 00000000000000000000000000000000000000000010000000000000000000000000000000000000000000100000000010000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000 000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
16776
result:
ok 1 number(s): "16776"
Test #24:
score: 0
Accepted
time: 269ms
memory: 4572kb
input:
10 100000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
2000000000000
result:
ok 1 number(s): "2000000000000"
Test #25:
score: 0
Accepted
time: 1591ms
memory: 72048kb
input:
100000 10 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111111111 1111...
output:
200000000
result:
ok 1 number(s): "200000000"
Test #26:
score: 0
Accepted
time: 329ms
memory: 102360kb
input:
5000 200 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
4000000000
result:
ok 1 number(s): "4000000000"
Test #27:
score: 0
Accepted
time: 259ms
memory: 4692kb
input:
200 5000 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
100000000000
result:
ok 1 number(s): "100000000000"
Test #28:
score: 0
Accepted
time: 409ms
memory: 102412kb
input:
5000 200 01011011001100110010110011101100111001100010110000011111011010111011010100111001011000110010011100101111110001010101101100100001111001011111110100011101011011111101010111111101000000000000110010010100 010110110011001100101100111011001110011000101100000111110110101110110101001110010110001100...
output:
2834691058
result:
ok 1 number(s): "2834691058"
Test #29:
score: 0
Accepted
time: 260ms
memory: 4416kb
input:
50 20000 111100111010100100001111000001011000000100101110101011000101000000001101100110000110110011001000101000000000000010111101001000100010100000000000010101100011110100000010011110110111100110111100101010100011111100000110100100011100100001001011110010010101010001010011001100000100001100011111010...
output:
177674291006
result:
ok 1 number(s): "177674291006"
Test #30:
score: 0
Accepted
time: 1447ms
memory: 71904kb
input:
100000 10 1011010110 1000000000 0100111001 1010000100 1000111011 1011110101 1010011001 0110001010 1110010110 0000000001 0101110011 1100000111 0100101100 0111101111 1100101001 1001100110 1011110111 0111000010 1011101111 0011100010 0100100011 1111010111 0010000011 0001000100 0100101010 1001100001 1010...
output:
14
result:
ok 1 number(s): "14"
Test #31:
score: 0
Accepted
time: 364ms
memory: 8088kb
input:
999 999 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
19939999183
result:
ok 1 number(s): "19939999183"
Test #32:
score: 0
Accepted
time: 365ms
memory: 8240kb
input:
999 999 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok 1 number(s): "0"