結果
問題 |
No.1181 Product Sum for All Subsets
|
ユーザー |
|
提出日時 | 2021-06-14 13:55:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 895 bytes |
コンパイル時間 | 787 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 75,008 KB |
最終ジャッジ日時 | 2024-12-24 10:23:20 |
合計ジャッジ時間 | 3,343 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
""" 数列S=[x:1<=x<=k] len(S)=n k**n通り 集合T={x:1<=x<=n} n>len(T)>=0 2**n-1通り 1<=n<=2*10**5 1<=k<=10**18 数列Sを一つ固定したとする。 DPで計算可能 -> main0 全部まとめて計算する -> main1 """ def main0(n,k): mod=10**9+7 ret=0 for i in range(k**n): a=[] for j in range(n): a.append(i%k+1) i//=k dp=1 tmp=1 for x in a: # xを使わない遷移、xを使う遷移 dp=dp+dp*x dp%=mod tmp*=x tmp%=mod dp-=tmp dp%=mod ret+=dp ret%=mod return ret def main1(n,k): mod=10**9+7 sumk=(k*(k+1))//2 sumk%=mod dp=1 tmp=1 for i in range(n): # a[i]を使わない遷移、a[i]を使う遷移 dp=dp*k+dp*sumk dp%=mod tmp*=sumk tmp%=mod dp-=tmp dp%=mod return dp if __name__=='__main__': n,k=map(int,input().split()) ret1=main1(n,k) print(ret1)