結果

問題 No.214 素数サイコロと合成数サイコロ (3-Medium)
ユーザー 37zigen37zigen
提出日時 2020-09-23 20:54:21
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,049 ms / 3,000 ms
コード長 1,119 bytes
コンパイル時間 802 ms
コンパイル使用メモリ 11,100 KB
実行使用メモリ 31,076 KB
最終ジャッジ日時 2023-09-10 11:42:48
合計ジャッジ時間 4,624 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,049 ms
31,076 KB
testcase_01 AC 637 ms
30,572 KB
testcase_02 AC 1,035 ms
31,004 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import numpy as np

MOD=10**9+7

def mul(a, b, MOD=MOD):
    fft=np.fft
    def submul(f,g):
        L=len(f)+len(g)-1
        return fft.irfft(fft.rfft(f,L)*fft.rfft(g,L),L)%MOD
    al=a & (1<<15)-1
    bl=b & (1<<15)-1
    ah=a>>15
    bh=b>>15
    x,y,z=submul(al,bl),submul(ah,bh),submul(al+ah,bl+bh)
    x,y,z=map(lambda v:(v+.5).astype(np.int64),[x,y,z])
    return (x+(y<<30)+((z-x-y)<<15))%MOD


def coef_of_generating_function(P, Q, N):
    while N:
        Q1=Q.copy()
        Q1[1::2]=np.negative(Q1[1::2])
        P=mul(P,Q1)
        if N&1:
            P=P[1::2]
        else:
            P=P[::2]
        Q=mul(Q,Q1)[::2]
        N//=2
    return P[0]

def f(dice,n):
    U=(n+1)*dice[-1]
    dp=np.zeros((n+1,U+100),dtype=np.int64)
    dp[0][0]=1
    for add in dice:
        for i in range(n):
            for u in range(U):
                dp[i+1][u+add]+=dp[i][u]
                dp[i+1][u+add]%=MOD
    return dp[n]

N,P,C=map(int,input().split())
a=f([2,3,5,7,11,13],P)
b=f([4,6,8,9,10,12],C)
c=mul(a,b)
den=-c
den[0]=1
g=c[::-1].cumsum()[::-1]%MOD
g[0]=0
print(coef_of_generating_function(g,den,N))
0