QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563168 | #5215. 多项式 | Elegia | 0 | 0ms | 0kb | C++14 | 1.9kb | 2024-09-14 03:16:08 | 2024-09-14 03:16:09 |
answer
#include <bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
char s[19];
int trans[1 << 18][2][2];
int len;
ull ans[1 << 18], cur[1 << 18];
std::pair<unsigned, unsigned> rec(ull n, ll l, ll r) {
if (!n) {
memset(cur, 0, sizeof(ull) << len);
for (int i = l + 1; i <= r; ++i) cur[1 << (len - i - 1)] = 1;
return std::make_pair(1 << (len - l - 1), 1 << (len - r - 1));
}
unsigned x, y;
std::tie(x, y) = rec(n >> 1, l >> 1, r >> 1);
int b = n & 1;
static ull tmp[1 << 18];
memcpy(tmp, cur, sizeof(ull) << len); memset(cur, 0, sizeof(ull) << len);
for (int i = 0; i != 1 << len; ++i) {
cur[trans[i][b][0]] += tmp[i];
cur[trans[i][b][1]] += tmp[i];
}
if (r & 1) y = trans[y][b][1];
else { --cur[trans[y][b][1]]; y = trans[y][b][0]; }
if (l & 1) x = trans[x][b][1];
else { ++cur[trans[x][b][1]]; x = trans[x][b][0]; }
return std::make_pair(x, y);
}
int main() {
int T; std::cin >> T;
while (T--) {
int n, K; ull m, L, R; std::cin >> n >> m >> K >> L >> R >> s;
unsigned poly = 0;
for (int i = 0; i <= n; ++i) if (s[i] == '1') poly |= 1U << i;
--L; --R;
len = std::max(n, K);
for (unsigned i = 0; i != 1 << len; ++i) {
ull db = 0;
for (int j = 0; j != len; ++j) if ((i >> j) & 1)
db |= 1ULL << (j * 2);
trans[i][0][0] = db >> (len - 1); trans[i][0][1] = db >> len;
ull conv = 0;
for (int j = 0; j <= len; ++j) if ((poly >> j) & 1)
conv ^= db << j;
trans[i][1][0] = (conv >> (len - 1)) & ((1U << len) - 1);
trans[i][1][1] = (conv >> len) & ((1U << len) - 1);
}
memset(ans, 0, sizeof(ull) << K);
if (R - L + 1 >= K) {
rec(m, L + K - 2, R);
for (int i = 0; i != 1 << len; ++i) ans[i >> (len - K)] += cur[i];
}
std::cin >> s;
unsigned str = 0;
for (int i = 0; i != K; ++i) if (s[i] == '1') str |= 1U << i;
std::cout << ans[str] << '\n';
}
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 0
Runtime Error
input:
5 18 255 3 193 3017 1001101010000011000 001 18 253 18 1293 2712 1010000110010011000 000010100001100110 18 252 18 2952 3357 1011001011100001000 100000001000100010 18 407 18 430 5886 1101110011100111101 000000110000110111 18 182 18 488 1535 1100000101000001111 100010101010000000
output:
309
result:
Test #2:
score: 0
Time Limit Exceeded
input:
5 18 80741 3 113046 1098108 1000010011001101101 110 18 186066 18 379183 1273950 1100001001111100100 101000000010101010 18 65342 18 322809 1113891 1110001010011100110 000000000000000000 18 130725 18 696668 931741 1000000100001000110 000110000000000100 18 113795 18 362230 722989 1111100110001101011 01...
output:
130190
result:
Test #3:
score: 0
Time Limit Exceeded
input:
5 18 81147 3 559594 818348 1111011000011100110 101 18 191933 18 593665 685541 1111100011001111010 100000011000011100 18 133046 18 346553 1213199 1101110011100100010 000000000000000000 18 125311 18 1300971 1963986 1000000111001101011 010000000011111111 18 128938 18 539641 615508 1111110110110110110 0...
output:
23263
result:
Test #4:
score: 0
Time Limit Exceeded
input:
5 18 1124754010791117 3 15917328053323806 15917328053333805 1101100000011010110 011 18 6167665366246702 18 61997015219869231 61997015219879230 1000110000110001001 010000010101000101 18 8809208508473334 18 97755579845050183 97755579845060182 1000001010110000101 000000000000000000 18 4359323082579375 ...
output:
3002
result:
Test #5:
score: 0
Time Limit Exceeded
input:
5 18 4168028964839198 3 62021459821703506 62021459821713505 1101100011000110101 010 18 4215514569899004 18 32291817862183730 32291817862193729 1010110110111111110 000000000000010001 18 3939206564272093 18 30817088280979088 30817088280989087 1101110001111111111 000000000000000000 18 4458931866300106 ...
output:
689
result:
Test #6:
score: 0
Time Limit Exceeded
input:
5 18 3318821649576959 3 1 59738789692385263 1010101010110010010 010 18 8932084213448590 18 1 160777515842074621 1001010011011101011 010001010000000001 18 3024137999063000 18 1 54434483983134001 1011010100001001011 000000000000000000 18 7985615307930357 18 1 143741075542746427 1101100101000011001 001...
output:
1920582899626649
result:
Test #7:
score: 0
Time Limit Exceeded
input:
5 18 8843353483063335 3 1 159180362695140031 1001110101110100011 010 18 8861939083558521 18 1 159514903504053379 1111001100100100101 000101001100100100 18 6585502075962361 18 1 118539037367322499 1000110100100110111 000000000000000000 18 5452613326599807 18 1 98147039878796527 1000100000101111001 01...
output:
1558226805203856
result:
Test #8:
score: 0
Time Limit Exceeded
input:
5 18 8811341957968757 3 1 158604155243437627 1011110100111010000 111 18 3868973203778798 18 1 69641517668018365 1001110110111100011 010001010001000000 18 4503580210757614 18 1 81064443793637053 1101100010010011100 000000000000000000 18 8538377770565597 18 1 153690799870180747 1011001111010011101 011...
output:
4319830443900773
result:
Test #9:
score: 0
Time Limit Exceeded
input:
5 18 3937846058268005 3 29530711734766962 45306774363060944 1111100100001110111 011 18 8919890939165093 18 11485993709951403 22972461466332159 1101001101001101101 001001110000001000 18 7560021396029167 18 95310384128638507 111011783372160521 1101010110101011111 000000000000000000 18 1890057576206183...
output:
1639983992061345
result:
Test #10:
score: 0
Time Limit Exceeded
input:
5 18 2198507800083967 3 13843977297405656 28290158766768552 1001110101111100100 011 18 6648075433930527 18 75097479684218555 109866544362512076 1101000100100000011 110111111011110101 18 6522280426948423 18 11678940742830544 79553245882632684 1110011000001011100 000000000000000000 18 5248916496519897...
output:
10363812442773102