QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#563168#5215. 多项式Elegia0 0ms0kbC++141.9kb2024-09-14 03:16:082024-09-14 03:16:09

Judging History

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

  • [2024-09-14 03:16:09]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-09-14 03:16:08]
  • 提交

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

result: