結果

問題 No.1202 お菓子の食べ方
ユーザー qumazakiqumazaki
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 330 ms
116,396 KB
testcase_01 AC 339 ms
116,348 KB
testcase_02 AC 347 ms
116,408 KB
testcase_03 AC 342 ms
116,488 KB
testcase_04 AC 332 ms
116,512 KB
testcase_05 AC 332 ms
116,248 KB
testcase_06 AC 328 ms
116,440 KB
testcase_07 AC 336 ms
116,560 KB
testcase_08 AC 348 ms
116,352 KB
testcase_09 AC 342 ms
116,192 KB
testcase_10 AC 159 ms
100,688 KB
testcase_11 AC 181 ms
102,484 KB
testcase_12 AC 258 ms
108,248 KB
testcase_13 AC 164 ms
101,432 KB
testcase_14 AC 250 ms
108,452 KB
testcase_15 AC 156 ms
100,516 KB
testcase_16 AC 225 ms
105,500 KB
testcase_17 AC 188 ms
102,468 KB
testcase_18 AC 184 ms
102,700 KB
testcase_19 AC 165 ms
101,980 KB
testcase_20 AC 228 ms
106,252 KB
testcase_21 AC 232 ms
106,664 KB
testcase_22 AC 166 ms
101,612 KB
testcase_23 AC 207 ms
104,412 KB
testcase_24 AC 215 ms
104,944 KB
testcase_25 AC 163 ms
101,048 KB
testcase_26 AC 230 ms
107,296 KB
testcase_27 AC 212 ms
105,680 KB
testcase_28 AC 173 ms
101,648 KB
testcase_29 AC 180 ms
103,424 KB
testcase_30 AC 104 ms
82,912 KB
testcase_31 AC 111 ms
83,524 KB
testcase_32 AC 107 ms
82,640 KB
testcase_33 AC 108 ms
82,664 KB
testcase_34 AC 104 ms
82,712 KB
testcase_35 AC 115 ms
82,952 KB
testcase_36 AC 112 ms
83,140 KB
testcase_37 AC 110 ms
82,316 KB
testcase_38 AC 113 ms
82,248 KB
testcase_39 AC 111 ms
82,308 KB
testcase_40 AC 339 ms
116,200 KB
testcase_41 AC 354 ms
116,232 KB
testcase_42 AC 339 ms
116,988 KB
testcase_43 AC 329 ms
116,468 KB
testcase_44 AC 336 ms
116,192 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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