jsで二項係数のmodの計算が合わない
Q&A
Closed
二項係数のmodの計算が合わない
以下問題を解いています。
発生している問題・エラー
jsを用いて、拡張Euclide互除法で逆元を計算しています。
大きい数字だと答えが合わず、どこが悪いのかわかりません。。
function main($) {
z = $.split(' ').map(Number)
let x, y;
[x, y] = z
if ((x + y) % 3 !== 0) {
console.log(0)
return
}
b = (2 * x - y) / 3
a = x - 2 * b
if (a < 0 || b < 0) {
console.log(0)
return
}
mod=1e9+7, max=a+b+1
fac=Array(max), inv=Array(max), finv=Array(max)
pre=()=>{
fac[0]=fac[1]=1,inv[1]=1,finv[0]=finv[1]=1
for (i=2;i<max;i++) {
fac[i]=fac[i-1]*i%mod
inv[i]=mod-inv[mod%i]*(mod/i|0)%mod
finv[i]=finv[i-1]*inv[i]%mod
}
}
modC=(n,k)=>{if(n<k)return 0;if(n<0||k<0)return 0;return fac[n]*(finv[k]*finv[n-k]%mod)%mod}
pre()
console.log(modC(a+b, a))
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'))
問題のサンプルでテストした際のエラー
[INFO] online-judge-tools 11.5.1 (+ online-judge-api-client 10.10.1)
[INFO] 3 cases found
[INFO] sample-1
[INFO] time: 0.032846 sec
[SUCCESS] AC
[INFO] sample-2
[INFO] time: 0.028956 sec
[SUCCESS] AC
[INFO] sample-3
[INFO] time: 0.116753 sec
[FAILURE] WA
input:
999999_999999
output:
599949243
expected:
151840682
[INFO] slowest: 0.116753 sec (for sample-3)
[INFO] max memory: 66.224000 MB (for sample-3)
[FAILURE] test failed: 2 AC / 3 cases
0
