結果

問題 No.1815 K色問題
ユーザー hotman78hotman78
提出日時 2022-09-18 09:24:24
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 2,199 bytes
コンパイル時間 89 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 32,276 KB
最終ジャッジ日時 2024-03-13 11:33:38
合計ジャッジ時間 3,975 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
20,244 KB
testcase_01 AC 34 ms
13,440 KB
testcase_02 WA -
testcase_03 AC 34 ms
13,440 KB
testcase_04 AC 34 ms
13,440 KB
testcase_05 WA -
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# okkuuさんのやつの書き換え
def main():
    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=(b*a)%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=(b*a)%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=(b*a)%mod
                a=(a*a)%mod
                mm>>=1
            tmp=(b*x)%mod
        if n==3:
            a00=(-13+i*14-i*i*6+i*i*i)%mod
            a01=(-10+i*13-i*i*6-i*i*i)%mod
            a10=(5-i*4+i*i)%mod
            a11=(3-i*3+i*i)%mod
            x=(i*2-i*i*3+i*i*i)%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)
if __name__ == '__main__':
    main()
0