結果

問題 No.215 素数サイコロと合成数サイコロ (3-Hard)
ユーザー 37zigen37zigen
提出日時 2020-09-23 21:39:44
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 2,553 ms / 4,000 ms
コード長 1,074 bytes
コンパイル時間 943 ms
コンパイル使用メモリ 11,032 KB
実行使用メモリ 52,392 KB
最終ジャッジ日時 2023-09-10 13:05:38
合計ジャッジ時間 10,930 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,490 ms
52,164 KB
testcase_01 AC 2,553 ms
52,392 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):
            dp[i+1,add:]+=dp[i,:-add]
            dp[i+1]%=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