結果

問題 No.2265 Xor Range Substring Sum Query
ユーザー fiblonariafiblonaria
提出日時 2023-04-11 15:13:24
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 926 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 146,652 KB
最終ジャッジ日時 2024-10-07 08:15:08
合計ジャッジ時間 8,133 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,224 KB
testcase_01 AC 41 ms
52,480 KB
testcase_02 AC 88 ms
67,456 KB
testcase_03 AC 114 ms
76,672 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def change(index, value):
	diff = value - dp[0][index]
	for i in range(1 + N // 2):
		for j in range(2 ** i):
			dp[i][j ^ index] += diff * p(11, 2 ** i - j - 1) * p(2, j)
			dp[i][j ^ index] %= mod
def calc(L, R, X):
	if L == R:
		return 0
	temp = 1
	key = 0
	while L % temp == 0 and R - L >= temp and key < N // 2 + 1:
		temp *= 2
		key += 1
	temp //= 2
	return (dp[key - 1][X ^ L] * p(11, R - L - temp) + calc(L + temp, R, X) * p(2, temp)) % mod
def p(a, r):
	rem = r % (mod - 1)
	ans = 1
	while rem:
		if rem%2:
			ans = (ans * a) % mod
		rem //= 2
		a = (a * a) % mod
	return ans
N = int(input())
S = list(map(int, list(input())))
Q = int(input())
mod = 998244353
dp = [[0 for i in range(2 ** N)] for j in range(1 + N // 2)]
query = [[1, i, S[i]] for i in range(2 ** N)] + [list(map(int, input().split())) for i in range(Q)]
for q in query:
	if q[0] == 1:
		change(*q[1:])
	else:
		print(calc(q[1], q[2] + 1, q[3]))
0