結果

問題 No.1815 K色問題
ユーザー okkuukenkenokkuukenken
提出日時 2022-01-12 17:10:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 416 ms / 2,000 ms
コード長 1,856 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 81,572 KB
実行使用メモリ 80,676 KB
最終ジャッジ日時 2024-03-13 11:29:57
合計ジャッジ時間 3,003 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
56,660 KB
testcase_01 AC 40 ms
56,660 KB
testcase_02 AC 40 ms
56,660 KB
testcase_03 AC 41 ms
56,660 KB
testcase_04 AC 40 ms
56,660 KB
testcase_05 AC 40 ms
56,660 KB
testcase_06 AC 193 ms
67,072 KB
testcase_07 AC 88 ms
67,456 KB
testcase_08 AC 316 ms
71,248 KB
testcase_09 AC 95 ms
67,824 KB
testcase_10 AC 112 ms
68,208 KB
testcase_11 AC 189 ms
80,676 KB
testcase_12 AC 40 ms
56,660 KB
testcase_13 AC 40 ms
56,660 KB
testcase_14 AC 416 ms
71,240 KB
testcase_15 AC 410 ms
71,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod=int(1e9+7)
fact=[0]*200001
invfact=[0]*200001
n,m,k=map(int,input().split())
fact[0]=1
for i in range(1,k+1):
    fact[i]=fact[i-1]*i%mod
for i in range(k+1):
    a=fact[i]
    mm=mod-2
    b=1
    while mm:
        if mm&1:
            b*=a
            b%=mod
        a*=a
        a%=mod
        mm>>=1
    invfact[i]=b
ans=0
for i in range(1,k+1):
    tmp=0
    if n==1:
        a=i-1
        x=i
        mm=m-1
        b=1
        while mm:
            if mm&1:
                b*=a
                b%=mod
            a*=a
            a%=mod
            mm>>=1
        tmp=b*x%mod
    if n==2:
        a=(i*i-3*i+3)%mod
        x=(i*i-i)%mod
        mm=m-1
        b=1
        while mm:
            if mm&1:
                b*=a
                b%=mod
            a*=a
            a%=mod
            mm>>=1
        tmp=b*x%mod
    if n==3:
        a00=(i*i*i-i*i*6+i*14-13)%mod
        a01=(i*i*i-i*i*6+i*13-10)%mod
        a10=(i*i-i*4+5)%mod
        a11=(i*i-i*3+3)%mod
        x=(i*i*i-i*i*3+i*2)%mod
        y=(i*i-i)%mod
        mm=m-1
        b00=1
        b01=0
        b10=0
        b11=1
        while mm:
            if mm&1:
                bb00=(b00*a00+b01*a10)%mod
                bb01=(b00*a01+b01*a11)%mod
                bb10=(b10*a00+b11*a10)%mod
                bb11=(b10*a01+b11*a11)%mod
                b00=bb00
                b01=bb01
                b10=bb10
                b11=bb11
            aa00=(a00*a00+a01*a10)%mod
            aa01=(a00*a01+a01*a11)%mod
            aa10=(a10*a00+a11*a10)%mod
            aa11=(a10*a01+a11*a11)%mod
            a00=aa00
            a01=aa01
            a10=aa10
            a11=aa11
            mm>>=1
        tmp=(b00*x+b01*y+b10*x+b11*y)%mod
    tmp*=fact[k]*invfact[i]%mod*invfact[k-i]%mod
    tmp%=mod
    if(k-i)&1:
        tmp=(-tmp+mod)%mod
    ans+=tmp
    ans%=mod
print(ans)
0