結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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=0
  while g in mex:
    g+=1
  memo[(n,x,bit)]=g
  return g

mod=998244353

def solve(n,x):
  if x%2==1:
    lose=n//2
    return ((n-lose)%mod)
  n+=2
  N=n
  m=x//2+1
  lose=(n//(2*(x+3)))*(x+2)
  n%=(2*(x+3))
  lose+=min(x//2+1,n//2+1)
  n-=x+3
  lose+=max(0,min(x//2+1,n//2+1))
  lose-=2
  N-=2
  ans=N-lose
  return (ans%mod)

def naive(n,x):
  ans=0
  for i in range(1,n+1):
    if calc(i,x,0)!=0:
      ans+=1
  return ans


for _ 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))
0