結果

問題 No.931 Multiplicative Convolution
ユーザー msm1993msm1993
提出日時 2020-10-29 17:40:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 2,737 bytes
コンパイル時間 443 ms
コンパイル使用メモリ 53,032 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-07-21 22:36:06
合計ジャッジ時間 3,258 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 3 ms
6,940 KB
testcase_07 AC 12 ms
6,940 KB
testcase_08 AC 99 ms
11,264 KB
testcase_09 AC 86 ms
11,392 KB
testcase_10 AC 96 ms
11,264 KB
testcase_11 AC 87 ms
11,264 KB
testcase_12 AC 54 ms
7,552 KB
testcase_13 AC 122 ms
11,324 KB
testcase_14 AC 104 ms
11,392 KB
testcase_15 AC 96 ms
11,264 KB
testcase_16 AC 95 ms
11,392 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:82:56: warning: 'x' may be used uninitialized [-Wmaybe-uninitialized]
   82 |         for (int i = 1; i < n; i++) p[i] = (p[i - 1] * x) % pn;
      |                                                        ^
main.cpp:63:24: note: 'x' was declared here
   63 |         int n, sz = 1, x, pn;
      |                        ^

ソースコード

diff # 

bool debug = false;
#include <stdio.h>
#include <vector>
using namespace std;
constexpr int kMod = 998244353, kN = int(1E5 + 10);
typedef long long int ll;
ll Pow(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = (ans * a) % kMod;
		b >>= 1;
		a = (a * a) % kMod;
	}
	return ans;
}
ll Rev(ll n) {return Pow(n, kMod - 2);}

void Ntt(vector<ll> &v, bool on, int sz) {
	ll wn, w, u, t, inv;
	for (int i = 1, j = sz >> 1, k; i < (sz - 1); i++) {
		if (i < j) swap(v[i], v[j]);
		k = sz >> 1;
		while (j & k) {
			j ^= k;
			k >>= 1;
		}
		j |= k;
	}	
	for (int i = 2; i <= sz; i <<= 1) {
		wn = on ? Pow(3, (kMod - 1) / i) : Pow(3, kMod - 1 - (kMod - 1) / i);
		for (int j = 0; j < sz; j += i) {
			w = 1;
			for (int k = j; k < j + (i >> 1); k++) {
				u = v[k];
				t = (w * v[k + (i >> 1)]) % kMod;
				v[k] = (u + t) % kMod;
				v[k + (i >> 1)] = (u - t + kMod) % kMod;
				w = (w * wn) % kMod;
			}
		}
	}
	if (on) {
		inv = Rev(sz);
		for (int i = 0; i < sz; i++) v[i] = (v[i] * inv) % kMod;
	}
	return ;
}

bool ok(int n, int pn) {
	int cnt = 2;
	ll now = n * n % pn;
	while (now != n) {
		now = (now * n) % pn;
		cnt++;
	}
	return cnt == pn;
}

ll p[kN], rp[kN];
int a[kN], b[kN];

int main() {
	int n, sz = 1, x, pn;
	vector<ll> va, vb, vc;
	scanf("%d", &n);
	pn = n;
	n--;
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	for (int i = 0; i < n; i++) scanf("%d", &b[i]);
	while (sz < n) sz <<= 1;
	sz <<= 1;
	if (debug) printf("sz = %d\n", sz);
	va.resize(sz);
	vb.resize(sz);
	vc.resize(sz);
	for (int i = 2; i < pn; i++) if (ok(i, pn)) {
		x = i;
		break;
	}
	if (debug) printf("x = %d\n", x);
	p[0] = 1;
	for (int i = 1; i < n; i++) p[i] = (p[i - 1] * x) % pn;
	for (int i = 0; i < n; i++) p[i]--;
	for (int i = 0; i < n; i++) rp[p[i]] = i;
	if (debug) {
		printf("p::");
		for (int i = 0; i < n; i++) printf(" %lld", p[i]);
		printf("\n");
		printf("rp::");
		for (int i = 0; i < n; i++) printf(" %lld", rp[i]);
		printf("\n");
	}	
	for (int i = 0; i < n; i++) va[i] = a[p[i]];
	for (int i = 0; i < n; i++) vb[i] = b[p[i]];
	if (debug) {
		printf("va::");
		for (int i = 0; i < sz; i++) printf(" %lld", va[i]);
		printf("\n");
	}
	if (debug) {
		printf("vb::");
		for (int i = 0; i < sz; i++) printf(" %lld", vb[i]);
		printf("\n");
	}
	Ntt(va, false, sz);
	Ntt(vb, false, sz);
	for (int i = 0; i < sz; i++) vc[i] = (va[i] * vb[i]) % kMod;
	Ntt(vc, true, sz);
	if (debug) {
		printf("vc::");
		for (int i = 0; i < sz; i++) printf(" %lld", vc[i]);
		printf("\n");
	}
	for (int i = n; i < sz; i++) vc[i % n] += vc[i];
	for (int i = 0; i < n; i++) vc[i] %= kMod;
	for (int i = 0; i < n; i++) if (vc[i] < 0) vc[i] += kMod;
	printf("%lld", vc[0]);
	for (int i = 1; i < n; i++) printf(" %lld", vc[rp[i]]);
	printf("\n");
}
0