結果

問題 No.931 Multiplicative Convolution
ユーザー ianCKianCK
提出日時 2019-12-10 00:19:17
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 117 ms / 2,000 ms
コード長 2,858 bytes
コンパイル時間 444 ms
コンパイル使用メモリ 41,600 KB
実行使用メモリ 11,336 KB
最終ジャッジ日時 2024-06-23 09:52:41
合計ジャッジ時間 3,290 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:65:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   65 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:68:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |         for (int i = 0; i < n; i++) scanf("%d", &a[i]);
      |                                     ~~~~~^~~~~~~~~~~~~
main.cpp:69:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |         for (int i = 0; i < n; i++) scanf("%d", &b[i]);
      |                                     ~~~~~^~~~~~~~~~~~~
main.cpp:82:56: warning: ‘x’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |         for (int i = 1; i < n; i++) p[i] = (p[i - 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