結果

問題 No.834 Random Walk Trip
コンテスト
ユーザー titia
提出日時 2026-02-04 03:50:52
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 254 ms / 2,000 ms
コード長 1,540 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 291 ms
コンパイル使用メモリ 82,884 KB
実行使用メモリ 245,772 KB
最終ジャッジ日時 2026-02-04 03:51:01
合計ジャッジ時間 8,154 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

mod=10**9+7

FACT=[1]
for i in range(1,2*10**6+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**6,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]%mod*FACT_INV[a-b]%mod
    else:
        return 0

N,M=map(int,input().split())

if N==1:
    print(1)
else:
    ANS=0

    for i in range(10**6):

        x=0+(2*N)*i

        # left-right=x,left+right=M
        # left=(x+M)/2 right=M-left

        if (x+M)%2!=0:
            continue

        left=(x+M)//2
        right=M-left

        if left<0 or right<0:
            continue

        if i==0:
            #print(left,right)
            ANS+=Combi(left+right,left)
        else:
            #print(left,right)
            ANS+=Combi(left+right,left)*2


    for i in range(10**6):

        x=-1+(2*N)*i

        if (x+M)%2!=0:
            pass
        else:
            left=(x+M)//2
            right=M-left

            if left<0 or right<0:
                pass
            else:
                #print(left,right)
                ANS+=Combi(left+right,left)

        x=-1-(2*N)*i

        if (x+M)%2!=0:
            pass
        else:
            left=(x+M)//2
            right=M-left

            if left<0 or right<0:
                pass
            else:               
                if i>0:
                    #print(left,right)
                    ANS+=Combi(left+right,left)

    print(ANS%mod)
0