[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 131 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
178: 2023/10/07(土)00:39 AAS
ごめん、一瞬数え上げと勘違いしてそう書いたけど普通に嘘だった
数え上げの場合、1+x^wiをFFTしたあとに各点でki乗して全商品で総積を取り、逆FFTで戻せばO(M(?logki+NlogM))で解ける的な話
実際の問題の方もmax-plus代数で考えて0+vi x^wiの積を取る話にすればFPSにはなるけど、max-plus代数の畳み込みは凸性がないと高速化できないし、操作としては結局ただナップサックDPやるのと変わらない
上下前次1-新書関写板覧索設栞歴
あと 824 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.007s