結果

問題 No.1145 Sums of Powers
ユーザー kouty
提出日時 2025-02-20 05:36:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 288 ms / 2,000 ms
コード長 2,578 bytes
コンパイル時間 5,911 ms
コンパイル使用メモリ 320,340 KB
実行使用メモリ 25,940 KB
最終ジャッジ日時 2025-02-20 05:36:41
合計ジャッジ時間 7,521 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#include<atcoder/modint>
using namespace atcoder;
using mint = modint998244353;

#include<atcoder/convolution>

vector<mint> inv_table;

vector<mint> fps_inv(vector<mint> f , int d = -1){
	assert(f[0].val() != 0);
	int N = (int)f.size();
	if(d == -1)d = N;
	vector<mint> g(1);
	g[0] = mint(1) / f[0];
	for(int i = 0; (1<<i) < d; i++){
		int len = min(d , 1<<(i+1));
		vector<mint> tmp(len);
		for(int j = 0; j < min(N , len); j++)tmp[j] = -f[j];
		tmp = convolution(g , tmp);
		tmp[0] += 2;
		g = convolution(g , tmp);
		g.resize(len);
	}
	return g;
}

vector<mint> fps_diff(vector<mint> f , int d = -1){
	int N = (int)f.size();
	if(d == -1)d = N-1;
	vector<mint> g(d);
	for(int i = 1; i < min(d , N); i++){
		g[i-1] = f[i] * i;
	}
	return g;
}

vector<mint> fps_integral(vector<mint> f , int d = -1){
	int N = (int)f.size();
	if(d == -1)d = N;
	vector<mint> g(d);
	for(int i = 0; i < d-1; i++){
		g[i+1] = f[i] * inv_table[i+1];
	}
	return g;
}

vector<mint> fps_log(vector<mint> f , int d = -1){
	assert(f[0].val() == 1);
	int N = (int)f.size();
	if(d == -1)d = N;
	vector<mint> f_p = fps_diff(f , d);
	vector<mint> g = convolution(f_p , fps_inv(f , d));
	g.resize(d);
	g = fps_integral(g , d);
	g.resize(d);
	return g;
}

vector<mint> fps_exp(vector<mint> f , int d = -1){
	assert(f[0].val() == 0);
	int N = (int)f.size();
	if(d == -1)d = N;
	vector<mint> g(1);
	g[0] = 1;
	for(int i = 0; (1<<i) < d; i++){
		int len = min(d , 1<<(i+1));
		vector<mint> tmp = fps_log(g , d);
		tmp.resize(len);
		for(int j = 0; j < len; j++)tmp[j] = f[j] - tmp[j];
		tmp[0] += 1;
		g = convolution(g , tmp);
		g.resize(len);
	}
	return g;
}

// $B&2(B(A_i)^j (j = 0,..,K-1)
vector<mint> fps_powers_sum(vector<mint> A , int K){ 	
	int N = (int)A.size();
	vector<vector<mint>> f(N);
	for(int i = 0; i < N; i++){
		f[i] = {1 , -A[i]};
	}
	queue<int> q;
	for(int i = 0; i < N; i++)q.push(i);
	while(q.size() > 1){
		int x = q.front();
		q.pop();
		int y = q.front();
		q.pop();
		if(x > y)swap(x , y);
		f[x] = convolution(f[x] , f[y]);
		q.push(x);
	}
	f[0].resize(K);
	vector<mint> ret = fps_log(f[0] , K);
	for(int i = 1; i < K; i++){
		ret[i] = -ret[i] * i;
	}
	ret[0] = N;
	return ret;
}

int main(){
	int N; cin >> N;
	int K; cin >> K;
	vector<mint> A(N);
	for(int i = 0; i < N; i++){
		int a; cin >> a;
		A[i] = a;
	}
	inv_table.resize(K+2);
	for(int i = 1; i <= K+1; i++)inv_table[i] = mint(1) / i;
	vector<mint> ans = fps_powers_sum(A , K+1);
	for(int i = 1; i <= K; i++)cout << ans[i].val() << ' ';
	cout << endl;
}
0