結果

問題 No.1145 Sums of Powers
コンテスト
ユーザー SSRS
提出日時 2020-07-31 23:11:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,908 bytes
コンパイル時間 2,925 ms
コンパイル使用メモリ 208,308 KB
実行使用メモリ 368,644 KB
最終ジャッジ日時 2024-07-06 21:08:29
合計ジャッジ時間 6,449 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
unordered_map<long long, long long> mp;
long long modpow(long long a, long long b){
  if (mp.count(b)){
    return mp[b];
  } else {
    long long ans = 1;
    while (b > 0){
      if (b % 2 == 1){
        ans *= a;
        ans %= MOD;
      }
      a *= a;
      a %= MOD;
      b /= 2;
    }
    mp[b] = ans;
    return mp[b];
  }
}
unordered_map<long long, long long> mp2;
long long modinv(long long a){
  if (mp2.count(a)){
    return mp2[a];
  } else {
    mp2[a] = modpow(a, MOD - 2);
    return mp2[a];
  }
}
vector<long long> ntt(vector<long long> A, bool inv){
	int N = A.size();
	int M = 0;
	for (int i = 1; i < N; i *= 2){
		M++;
	}
	for (int i = 0; i < N; i++){
		int j = 0;
		for (int k = 0; k < M; k++){
			if ((i >> k) & 1){
				j |= 1 << (M - 1 - k);
			}
		}
		if (i < j){
			swap(A[i], A[j]);
		}
	}
	for (int i = 1; i < N; i *= 2){
		long long z = modpow(3, (MOD - 1) / (i * 2));
		if (inv){
			z = modinv(z);
		}
		long long z2 = 1;
		for (int j = 0; j < i; j++){
			for (int k = 0; k < N; k += i * 2){
				long long s = A[j + k];
				long long t = A[j + k + i] * z2 % MOD;
				A[j + k] = (s + t) % MOD;
				A[j + k + i] = (s - t + MOD) % MOD;;
			}
			z2 = z2 * z % MOD;
		}
	}
	if (inv){
		int Ninv = modinv(N);
		for (int i = 0; i < N; i++){
			A[i] = A[i] * Ninv % MOD;
		}
	}
	return A;
}
vector<long long> convolution(vector<long long> &A, vector<long long> &B, int d = 0){
	int deg = A.size() + B.size() - 1;
	if (d == 0){
	  d = deg;
	}
	int N = 1;
	while (N < deg){
		N *= 2;
	}
	while (A.size() < N){
		A.push_back(0);
	}
	while (B.size() < N){
		B.push_back(0);
	}
	vector<long long> a = ntt(A, false);
	vector<long long> b = ntt(B, false);
	vector<long long> c(N);
	for (int i = 0; i < N; i++){
		c[i] = a[i] * b[i] % MOD;
	}
	c = ntt(c, true);
	vector<long long> ans(d);
	for (int i = 0; i < d; i++){
		ans[i] = c[i];
	}
	return ans;
}
vector<long long> add(vector<long long> A, vector<long long> B){
  int N = max(A.size(), B.size());
  while (A.size() < N){
    A.push_back(0);
  }
  while (B.size() < N){
    B.push_back(0);
  }
  vector<long long> ans(N, 0);
  for (int i = 0; i < N; i++){
    ans[i] = A[i] + B[i];
    if (ans[i] > MOD){
      ans[i] -= MOD;
    }
  }
  return ans;
}
vector<long long> inverse(vector<long long> P){
  int N = P.size();
  vector<long long> ans(1);
  ans[0] = modinv(P[0]);
  for (int i = 1; i < N; i *= 2){
    vector<long long> ans2 = ans;
    ans2.resize(i * 4);
    vector<long long> f(min(N, i * 2));
    for (int j = 0; j < min(N, i * 2); j++){
      f[j] = P[j];
    }
    f.resize(i * 4);
    ans2 = convolution(ans2, ans2);
    ans2 = convolution(ans2, f);
    ans2.resize(i * 2);
    for (int j = 0; j < i; j++){
      ans2[j] = MOD - ans2[j] + ans[j] * 2;
      ans2[j] %= MOD;
    }
    swap(ans, ans2);
  }
  ans.resize(N);
  return ans;
}
int main(){
  int N, M;
  cin >> N >> M;
  vector<long long> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  int N2 = 1;
  while (N2 < N){
    N2 *= 2;
  }
  while (A.size() < N2){
    A.push_back(0);
  }
  N = N2;
  vector<pair<vector<long long>, int>> ST1(N2 * 2 - 1);
  for (int i = 0; i < N; i++){
    vector<long long> f = {1, MOD - A[i]};
    ST1[N2 - 1 + i] = make_pair(f, 1);
  }
  for (int i = N2 - 2; i >= 0; i--){
    int deg = min(M + 1, ST1[i * 2 + 1].second + ST1[i * 2 + 2].second + 1);
    ST1[i] = make_pair(convolution(ST1[i * 2 + 1].first, ST1[i * 2 + 2].first, deg), deg);
  }
  
  while (ST1[0].first.size() <= M * 2){
    ST1[0].first.push_back(0);
  }
  /*
  for (int i = 0; i <= M; i++){
    cout << ST1[0].first[i] << ' ';
  }
  cout << endl;
  */
  vector<pair<vector<long long>, int>> ST2(N2 * 2 - 1);
  for (int i = 0; i < N; i++){
    vector<long long> f = {1};
    ST2[N2 - 1 + i] = make_pair(f, 1);
  }
  for (int i = N2 - 2; i >= 0; i--){
    if (ST2[i * 2 + 2].second == 0){
      ST2[i] = ST2[i * 2 + 1];
    } else {
      int deg = min(M + 1, ST2[i * 2 + 1].second + ST2[i * 2 + 2].second);
      ST2[i] = make_pair(add(convolution(ST2[i * 2 + 1].first, ST1[i * 2 + 2].first, deg), convolution(ST1[i * 2 + 1].first, ST2[i * 2 + 2].first, deg)), deg);
    }
  }
  
  while (ST2[0].first.size() <= M * 2){
    ST2[0].first.push_back(0);
  }
  /*
  for (int i = 0; i <= M; i++){
    cout << ST2[0].first[i] << ' ';
  }
  cout << endl;
  
  */
  vector<long long> g = ST1[0].first;
  vector<long long> f = ST2[0].first;
  
  //f/g
  vector<long long> g_inv = inverse(g);
  /*
  vector<long long> h = convolution(g, g_inv);
  for (int i = 0; i <= M; i++){
    cout << h[i] << ' ';
  }
  cout << endl;
  */
  vector<long long> ans = convolution(f, g_inv);
  for (int i = 1; i <= M; i++){
    cout << ans[i];
    if (i < M){
      cout << ' ';
    }
  }
  cout << endl;
}
0