[問題案] Subset Sum

[Maruoka842]

(任意) 問題ID: {subset_sum} 問題名: {Subset Sum}

(任意) 参考資料: { https://arxiv.org/pdf/1807.11597.pdf }

問題概要

想定１ n個の正整数s_1,s_2,\ldots,snと正整数tが与えられます。 部分集合I\subseteq {1,2,...,n}のうち\sum{i\in I} s_i=t \bmod 998244353なるものの個数を数えてください。

想定２(subset sumとの関連が分かりづらい？)

\prod_{i=0}^n (1+x^{si}) \mod x^{t+1}を998244353で割った余り\sum{i=0}^t b_ix^iを求めてください。

入力

n
t
s_1
s_2
\vdots
s_n

出力(想定1なら省略)

b_0 b_1 \dots b_{t-1}

制約

1 \neq n \neq 1000000
1 \leq t \leq 500000
1 \leq s_i  \leq t

[yosupo06]

• 想定1の「部分集合I\subseteq {1,2,...,n}のうち\sum_{i\in I} si=t \bmod 998244353なるものの個数を数えてください。」これは「部分集合I\subseteq {1,2,...,n}のうち\sum{i\in I} s_i=tとなるものの個数 \bmod 998244353を数えてください。」でしょうか？
• 速度の実測の情報などはありますでしょうか？(O^~記法を使っているので、めちゃくちゃ遅くてもおかしくないなと思っています)

[tko919]

N=1000000,T=500000で1.3sくらいでした(AtCoderのコードテスト) Verify出来てないですが自作のランダムケースは通ったので合ってると思います

[yosupo06]

• 想定1か、想定1でt=0,1,...をすべて出させるか　がいいと思います
• 名前がSubset sumだと判定版っぽくて、よくなさそう(論文中でも#_p Subset Sum problemと呼ばれていそう)
• 思ったより速いですね　全然良さそうです

[Maruoka842]

・「部分集合I\subseteq {1,2,...,n}のうち\sum_{i\in I} s_i=tとなるものの個数 \bmod 998244353を数えてください。」でしょうか？ →すみません、その通りです。 ・「想定1でt=0,1,...を出力」にします。 ・yosupo judgeで#_p Subset Sumという名前はありでしょうか？

[yosupo06]

わ、完全に返信見逃してました　すいません

・yosupo judgeで#_p Subset Sumという名前はありでしょうか？

既に何件かあるんですが、タイトルに数式はありです

[tko919]

すみません　これも僕が代行します タイトルはSubset Sumのままでやるかもしれません...

[Maruoka842]

部分集合 $I \subseteq {0,1,...,N-1}$ の { , } のエスケープが効いていません。

[yosupo06]

$I \subseteq \{0,1,...,N-1\}$ がpython.markdownに入れると $I \subseteq {0,1,...,N-1}$ になる…一体何が

[yosupo06]

この問題自体は一般的なので別issueにしましたが、それはそうとしてとりあえずこれは直しました(間違えてmasterにpushした…)

[beet-aizu]

n << t のケースが入っているといいかもしれません（間違えてn項目まででexpしても通ってしまったので） https://old.yosupo.jp/submission/33130