結果

問題 No.1202 お菓子の食べ方
コンテスト
ユーザー qumazaki
提出日時 2020-08-30 02:55:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 354 ms / 2,000 ms
コード長 1,745 bytes
コンパイル時間 643 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 116,988 KB
最終ジャッジ日時 2024-11-14 17:51:10
合計ジャッジ時間 13,230 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,m = map(int,readline().split())
s = [list(map(int,i.split())) for i in readlines()]
mod = 1_000_000_007

## nCkのmodを求める関数
# テーブルを作る(前処理)
max_n = 10**6 + 10**4
fac, finv, inv = [0]*max_n, [0]*max_n, [0]*max_n

def comInit(max_n):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max_n):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max_n)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

for i in range(n):
    s[i].append(0)

s.append([0]*(m+1))

ans = 0
for i in range(n+1):
    for j in range(m+1):
        if(i==n)&(j==m):
            continue
        if(s[i][j] > 0):
            move = i+j+s[i][j]-1
            tmp = com(move,i) * com(move-i,j)
            tmp %= mod
            ans += tmp

        #飛び降り
        if(i!=0):
            if(s[i-1][j] - s[i][j] > 0):
                tmp = com(i-1+j+s[i-1][j], s[i-1][j]-1)
                tmp -= com(i-1+j+s[i][j], s[i][j]-1)
                tmp %= mod
                tmp *= com(i-1+j,j)
                tmp %= mod
                ans += tmp
        if(j!=0):
            if(s[i][j-1] - s[i][j] > 0):
                tmp = com(i+j-1+s[i][j-1], s[i][j-1]-1)
                tmp -= com(i+j-1+s[i][j], s[i][j]-1)
                tmp %= mod
                tmp *= com(i+j-1,i)
                tmp %= mod
                ans += tmp

        ans %= mod
        # print(i,j,ans)

print(ans)
0