結果
問題 | No.2132 1 or X Game |
ユーザー |
![]() |
提出日時 | 2022-11-25 22:13:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 573 ms / 2,000 ms |
コード長 | 837 bytes |
コンパイル時間 | 348 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 77,056 KB |
最終ジャッジ日時 | 2024-10-02 04:46:04 |
合計ジャッジ時間 | 8,514 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 11 |
ソースコード
memo={}def calc(n,x,bit):if (n,x,bit) in memo:return memo[(n,x,bit)]mex=set()if n>0:mex.add(calc(n-1,x,bit>>1))if n>=x and bit&1==0:mex.add(calc(n-x,x,(bit>>1)+2))g=0while g in mex:g+=1memo[(n,x,bit)]=greturn gmod=998244353def solve(n,x):if x%2==1:lose=n//2return ((n-lose)%mod)n+=2N=nm=x//2+1lose=(n//(2*(x+3)))*(x+2)n%=(2*(x+3))lose+=min(x//2+1,n//2+1)n-=x+3lose+=max(0,min(x//2+1,n//2+1))lose-=2N-=2ans=N-losereturn (ans%mod)def naive(n,x):ans=0for i in range(1,n+1):if calc(i,x,0)!=0:ans+=1return ansfor _ in range(int(input())):n,x=map(int,input().split())print(solve(n,x))exit()for x in range(1,100):for n in range(1,100):if solve(n,x)!=naive(n,x):print(n,x,solve(n,x),naive(n,x))