結果

問題 No.1202 お菓子の食べ方
ユーザー qumazakiqumazaki
提出日時 2020-08-30 02:55:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 324 ms / 2,000 ms
コード長 1,745 bytes
コンパイル時間 249 ms
コンパイル使用メモリ 82,428 KB
実行使用メモリ 116,988 KB
最終ジャッジ日時 2024-04-27 01:29:36
合計ジャッジ時間 12,468 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 300 ms
116,580 KB
testcase_01 AC 290 ms
116,316 KB
testcase_02 AC 313 ms
116,276 KB
testcase_03 AC 294 ms
116,484 KB
testcase_04 AC 286 ms
116,344 KB
testcase_05 AC 306 ms
116,440 KB
testcase_06 AC 302 ms
116,556 KB
testcase_07 AC 291 ms
116,436 KB
testcase_08 AC 307 ms
116,988 KB
testcase_09 AC 299 ms
116,448 KB
testcase_10 AC 131 ms
101,368 KB
testcase_11 AC 151 ms
102,364 KB
testcase_12 AC 223 ms
108,160 KB
testcase_13 AC 144 ms
101,532 KB
testcase_14 AC 221 ms
108,208 KB
testcase_15 AC 128 ms
100,752 KB
testcase_16 AC 183 ms
105,700 KB
testcase_17 AC 157 ms
102,684 KB
testcase_18 AC 159 ms
103,052 KB
testcase_19 AC 141 ms
101,528 KB
testcase_20 AC 199 ms
106,352 KB
testcase_21 AC 201 ms
106,464 KB
testcase_22 AC 141 ms
101,424 KB
testcase_23 AC 181 ms
105,064 KB
testcase_24 AC 183 ms
104,724 KB
testcase_25 AC 135 ms
101,160 KB
testcase_26 AC 197 ms
107,544 KB
testcase_27 AC 185 ms
105,820 KB
testcase_28 AC 149 ms
101,528 KB
testcase_29 AC 171 ms
103,292 KB
testcase_30 AC 89 ms
81,836 KB
testcase_31 AC 94 ms
82,784 KB
testcase_32 AC 91 ms
82,492 KB
testcase_33 AC 91 ms
83,016 KB
testcase_34 AC 91 ms
82,988 KB
testcase_35 AC 92 ms
82,212 KB
testcase_36 AC 88 ms
83,380 KB
testcase_37 AC 91 ms
82,692 KB
testcase_38 AC 93 ms
82,572 KB
testcase_39 AC 97 ms
82,896 KB
testcase_40 AC 299 ms
116,600 KB
testcase_41 AC 324 ms
116,356 KB
testcase_42 AC 308 ms
116,488 KB
testcase_43 AC 312 ms
116,848 KB
testcase_44 AC 312 ms
116,420 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