結果
問題 | No.1503 Bitwise And Convolution Twisted |
ユーザー | chineristAC |
提出日時 | 2021-05-07 22:31:06 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,769 ms / 2,000 ms |
コード長 | 1,481 bytes |
コンパイル時間 | 808 ms |
コンパイル使用メモリ | 86,936 KB |
実行使用メモリ | 345,632 KB |
最終ジャッジ日時 | 2023-10-13 13:46:35 |
合計ジャッジ時間 | 10,422 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 99 ms
74,656 KB |
testcase_01 | AC | 102 ms
74,072 KB |
testcase_02 | AC | 101 ms
74,520 KB |
testcase_03 | AC | 103 ms
74,708 KB |
testcase_04 | AC | 96 ms
74,660 KB |
testcase_05 | AC | 101 ms
74,688 KB |
testcase_06 | AC | 282 ms
86,672 KB |
testcase_07 | AC | 534 ms
214,392 KB |
testcase_08 | AC | 251 ms
86,640 KB |
testcase_09 | AC | 1,575 ms
345,632 KB |
testcase_10 | AC | 1,769 ms
345,192 KB |
testcase_11 | AC | 1,438 ms
345,448 KB |
ソースコード
mod = 998244353 def andconv(n,X,Y): if n==0: res=[(X[0]*Y[0])%mod] return res x=[X[i]+X[i+2**(n-1)] for i in range(2**(n-1))] y=[Y[i]+Y[i+2**(n-1)] for i in range(2**(n-1))] z=[X[i+2**(n-1)] for i in range(2**(n-1))] w=[Y[i+2**(n-1)] for i in range(2**(n-1))] res1=andconv(n-1,x,y) res2=andconv(n-1,z,w) res1=[(res1[i]-res2[i])%mod for i in range(2**(n-1))] return res1+res2 def subset(n,X): if n==0: return [X[0]%mod] x = subset(n-1,X[:1<<(n-1)]) y = subset(n-1,X[1<<(n-1):]) for i in range(1<<(n-1)): y[i] += x[i] y[i] %= mod return x+y def isubset(n,X): if n==0: return [X[0]%mod] x = isubset(n-1,X[:1<<(n-1)]) y = isubset(n-1,X[1<<(n-1):]) for i in range(1<<(n-1)): y[i] = y[i] - x[i] y[i] %= mod return x+y import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import log,gcd input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) N = int(input()) A = li() B = li() A = A[::-1] A1 = subset(N,A) A1 = A1[::-1] B1 = isubset(N,B) C = [A1[k]*B1[k]%mod for k in range(1<<N)] C = subset(N,C) print(*C) """ C_n = \sum_{i subset n} B_i (\sum_{i subset j subset n} (-1)**(j-i) A1_j) = \sum_{i subset n} \sum_{j subset i} A1_i * (i-j) * B_j = \sum_{i subset n} A1_i B1_i """