結果

問題 No.2132 1 or X Game
ユーザー とりゐとりゐ
提出日時 2022-11-25 22:13:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 592 ms / 2,000 ms
コード長 837 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 76,844 KB
最終ジャッジ日時 2024-04-10 03:22:33
合計ジャッジ時間 8,464 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 36 ms
54,356 KB
testcase_01 AC 582 ms
76,260 KB
testcase_02 AC 592 ms
76,072 KB
testcase_03 AC 551 ms
76,472 KB
testcase_04 AC 559 ms
76,160 KB
testcase_05 AC 569 ms
76,404 KB
testcase_06 AC 547 ms
76,484 KB
testcase_07 AC 528 ms
76,272 KB
testcase_08 AC 566 ms
76,544 KB
testcase_09 AC 523 ms
76,844 KB
testcase_10 AC 516 ms
76,424 KB
testcase_11 AC 541 ms
76,408 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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