test/ordered_convolution.test.cpp

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

検証問題

依存ライブラリ

• 畳み込みの型別振り分け
• FFT
• FPS のブロック変換
• FPS の融合畳み込み
• FPS の定数係数畳み込み
• FPS の非対称畳み込み
• FPS の結果配列への一括変換
• FPS の作業領域
• modint998244353 の共通剰余演算
• modint998244353 の共有畳み込み
• NTT（998244353）（高速版）
• NTT（法指定）
• 実数・複素数の畳み込み
• 任意 mod・整数の畳み込み
• 一般の環の畳み込み
• i < j 制約付き畳み込み（高速版）
• modint998244353

コード

#define PROBLEM "https://yukicoder.me/problems/no/1307"
#include "../convolution/ordered_convolution.hpp"
#include "../math/mint.hpp"
#include <iostream>
#include <vector>

int main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int n, q;
	std::cin >> n >> q;
	std::vector<mint> a(n), b(n);
	for (auto &x : a) std::cin >> x;
	while (q--) {
		int r;
		std::cin >> r;
		b[(n - r) % n] += 1;
	}
	auto c = ordered_convolution(a, b), d = ordered_convolution(b, a);
	for (int i = 0; i < int(c.size()); ++i) c[i] += d[i];
	for (int i = 0; i < n; ++i) c[2 * i] += a[i] * b[i];
	for (int i = 0; i < n; ++i)
		std::cout << c[i] + (i + n < int(c.size()) ? c[i + n] : mint(0)) << (i + 1 == n ? '\n' : ' ');
}

Back to top page