test/power_projection.test.cpp

test/power_projection.test.cpp · GitHub で見る

検証問題

依存ライブラリ

• Fast I/O
• FPS のブロック変換
• FPS の合成・射影の共通変換
• FPS の合成・射影の汎用実装
• FPS の融合畳み込み
• FPS の定数係数畳み込み
• FPS の非対称畳み込み
• FPS と多項式除算の内部変換
• FPS の指数・冪の内部変換
• FPS の一点評価
• FPS 逆数のブロック変換
• FPS の内部演算
• FPS の結果配列への一括変換
• FPS の射影の専用変換
• 疎 FPS の共通演算
• 疎 FPS の次数圧縮・前処理
• 疎 FPS の項収集・演算種別
• FPS 平方根のブロック変換
• FPS の作業領域
• modint998244353 の共通剰余演算
• modint998244353 の共有畳み込み
• NTT（998244353）（高速版）
• 多項式の積・打ち切り積の共通処理
• 形式的冪級数（高速版）
• Power Projection（高速版）
• modint998244353

コード

#define PROBLEM "https://judge.yosupo.jp/problem/compositional_inverse_of_formal_power_series_large"
#include "fps/power_projection.hpp"
#include "fixtures/fps_io.hpp"

int main() {
	FastInput input;
	FastOutput output;
	int n = 0; input.read(n);
	auto f = read_fps(input, n);
	if (n == 1) {
		output.println(0);
		return 0;
	}
	auto p = power_projection(f, n - 1);
	fps inv(n), h(n - 1);
	inv[1] = 1;
	for (int i = 2; i < n; ++i) inv[i] = -mint(mint::mod() / i) * inv[mint::mod() % i];
	for (int i = 1; i < n; ++i) h[n - 1 - i] = p[i] * inv[i];
	h *= h[0].inv();
	h = h.log(n - 1);
	h *= -inv[n - 1];
	h = h.exp(n - 1);
	h *= f[1].inv();
	output.write('0'); output.write(' ');
	write_fps(output, h);
}

Back to top page