結果

問題 No.2265 Xor Range Substring Sum Query
ユーザー fiblonariafiblonaria
提出日時 2023-04-11 15:29:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 929 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 151,124 KB
最終ジャッジ日時 2024-10-07 08:34:38
合計ジャッジ時間 8,219 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
51,968 KB
testcase_01 AC 41 ms
51,968 KB
testcase_02 AC 69 ms
65,792 KB
testcase_03 AC 106 ms
76,288 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 * p11[2 ** i - j - 1] * p2[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] * p11[R - L - temp] + calc(L + temp, R, X) * p2[temp]) % mod
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)]
p2 = [1 for i in range(2 ** N)]
p11 = [1 for i in range(2 ** N)]
for i in range(1, 2 ** N):
	p2[i] = p2[i - 1] * 2 % mod
	p11[i] = p11[i - 1] * 11 % mod
for q in query:
	if q[0] == 1:
		change(*q[1:])
	else:
		print(calc(q[1], q[2] + 1, q[3]))
0