結果

問題 No.215 素数サイコロと合成数サイコロ (3-Hard)
ユーザー 37zigen37zigen
提出日時 2020-09-23 21:53:53
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,744 ms / 4,000 ms
コード長 967 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 11,148 KB
実行使用メモリ 49,516 KB
最終ジャッジ日時 2023-09-10 13:06:16
合計ジャッジ時間 5,466 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,554 ms
48,176 KB
testcase_01 AC 1,744 ms
49,516 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]=-Q1[1::2]
        P=mul(P,Q1)[N&1::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]
    return dp[n]

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