結果

問題 No.1879 How many matchings?
ユーザー taiga0629kyoprotaiga0629kyopro
提出日時 2022-08-20 04:44:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,728 bytes
コンパイル時間 376 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 64,064 KB
最終ジャッジ日時 2024-10-08 18:14:01
合計ジャッジ時間 2,047 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
53,076 KB
testcase_01 AC 36 ms
53,760 KB
testcase_02 WA -
testcase_03 AC 39 ms
54,100 KB
testcase_04 WA -
testcase_05 AC 39 ms
54,004 KB
testcase_06 WA -
testcase_07 AC 35 ms
53,820 KB
testcase_08 WA -
testcase_09 AC 51 ms
63,864 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 43 ms
62,992 KB
testcase_14 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 


#####################
mod=10**9+7
def mul(a,b):
    n=len(a)
    m=len(b[0])
    res=[[0]*m for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(len(a[0])):
                res[i][j]+=a[i][k]*b[k][j]
                res[i][j]%=mod
    return res
def add(a,b):
    res=[[0]*len(a[0]) for i in range(len(a))]
    for i in range(len(a)):
        for j in range(len(a[0])):
            res[i][j]=(a[i][j]+b[i][j])%mod
    return res
def mpow(a,n):
    N = len(a)
    if n == 0:
        res = [[0] * N for i in range(N)]
        for i in range(N):
            res[i][i] = 1
        return res
    if n==1:return a
    res=mpow(a,n//2)
    res=mul(res,res)
    if n%2==1:
        res=mul(res,a)
    return res


def det(A):
    a=[]
    for line in A:
        a.append(line[:])

    n=len(a)
    f=1
    for now in range(n):
        ind=-1
        for i in range(now,n):
            a[i][now]%=mod
            if a[i][now]>0:
                ind=i
                break
        if ind==-1:return 0
        a[now],a[ind]=a[ind],a[now]
        if now!=ind:f*=-1
        f=f*a[now][now]%mod
        inv=pow(a[now][now],mod-2,mod)
        for j in range(now,n):
            a[now][j]*=inv
            a[now][j]%=mod
        for i in range(now+1,n):
            x=a[i][now]
            for j in range(now,n):
                a[i][j]-=a[now][j]*x
                a[i][j]%=mod
    for i in range(n):
        f*=a[i][i]
        f%=mod
    return f


def minv(A):
    n=len(A)
    if det(A)==0:return -1
    a=[]
    for i in range(n):
        e=[0]*n
        e[i]=1
        a.append(A[i][:]+e)
    for now in range(n):
        ind = -1
        for i in range(now, n):
            a[i][now] %= mod
            if a[i][now] > 0:
                ind = i
                break
        if ind == -1: return -1
        a[now], a[ind] = a[ind], a[now]
        inv = pow(a[now][now], mod - 2, mod)
        for j in range(now, 2*n):
            a[now][j] *= inv
            a[now][j] %= mod
        for i in range(now + 1, n):
            x = a[i][now]
            for j in range(now, 2*n):
                a[i][j] -= a[now][j] * x
                a[i][j] %= mod
    for now in range(n-1,-1,-1):
        for i in range(now-1,-1,-1):
            x=a[i][now]
            for j in range(2*n):
                a[i][j]-=a[now][j]*x
                a[i][j]%=mod
    res=[]
    for l in a:res.append(l[n:])
    return res


#######################



n=int(input())

a=[[0]*4 for i in range(4)]
a[1][0]+=1
a[0][1]+=1
a[3][1]+=1
a[0][2]+=1
a[2][3]+=1
a=mpow(a,n-1)
ans=[[0] for i in range(4)]
ans[1][0]=1
ans=mul(a,ans)
res=0
if n%2==0:
    res=ans[0][0]
else:
    res=ans[0][0]+ans[1][0]+ans[2][0]
print(res%mod)
0