結果

問題 No.1145 Sums of Powers
ユーザー SSRSSSRS
提出日時 2020-08-01 02:41:19
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,537 bytes
コンパイル時間 2,173 ms
コンパイル使用メモリ 191,528 KB
実行使用メモリ 157,484 KB
最終ジャッジ日時 2024-07-07 01:46:56
合計ジャッジ時間 10,931 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 16 ms
6,940 KB
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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();
	long long r = 3;
	if (inv){
		r = modinv(r);
	}
	vector<long long> B(N);
	for (int i = N / 2; i > 0; i /= 2){
		long long z = modpow(r, (MOD - 1) / (N / i));
		long long z2 = 1;
		for (int j = 0; j < N; j += i * 2){
			for (int k = 0; k < i; k++){
				A[i + j + k] *= z2;
				A[i + j + k] %= MOD;
				B[j / 2 + k] = (A[j + k] + A[i + j + k]) % MOD;
				B[N / 2 + j / 2 + k] = (A[j + k] - A[i + j + k] + MOD) % MOD;
			}
			z2 = z2 * z % MOD;
		}
		swap(A, B);
	}
	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 = -1){
	int deg = A.size() + B.size() - 1;
	int N = 1;
	while (N < deg){
		N *= 2;
	}
	A.resize(N);
	B.resize(N);
	A = ntt(A, false);
	B = ntt(B, false);
	vector<long long> ans(N);
	for (int i = 0; i < N; i++){
		ans[i] = A[i] * B[i] % MOD;
	}
	ans = ntt(ans, true);
	if (d == -1){
    	ans.resize(deg);
	} else {
        ans.resize(d);
	}
	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, i * 2);
    ans2 = convolution(ans2, f, 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