10pts WA 不过样例,炸掉了
查看原帖
10pts WA 不过样例,炸掉了
906320
Milky_Cat楼主2024/12/17 07:51

已知多项式 ln\ln 能过板子,然后我看了半天也没看出这个 exp\exp 函数哪里写挂了。

于是调不出来,破防了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[4000005], b[4000005], tmp[4000005], tmp3[4000005], tmp2[4000005], fac[4000005], Inv[4000005], tmp4[4000005];
int n, m, l, r[4000005], p;
int lim = 1;
string aa, bb;
const int mod = 998244353;
int qpow(int x, int k){
	int ans = 1;
	while (k){
		if (k & 1)
			ans = ans * x % mod;
		x = x * x % mod;
		k >>= 1;
	}
	return ans;
}
void NTT(int *aa, int tp) {
    for (int i = 0; i < lim; i++)
        if (i < r[i])
            swap(aa[i], aa[r[i]]);
    for (int mid = 2; mid <= lim; mid <<= 1) {
        int omega = qpow(3, (mod - 1) / mid);
        for (int rr = mid >> 1, j = 0; j < lim; j += mid) {
            int omega2 = 1;
            for (int k = 0; k < rr; k++) {
                int xx = aa[j + k], yy = omega2 * aa[j + k + rr] % mod;
                aa[j + k] = (xx + yy) % mod;
                aa[j + k + rr] = (xx - yy + mod) % mod;
				omega2 = omega2 * omega % mod;
            }
        }
    }
    if (tp == -1){
    	reverse(aa + 1, aa + lim);
    	int inv = qpow(lim, mod - 2);
    	for (int i = 0; i < lim; i++)
    		aa[i] = aa[i] * inv % mod;
	}
}
void polyInv(int *a, int *b, int n){
	if (n == 1){
		b[0] = qpow(a[0], mod - 2) % mod;
		return;
	}
	polyInv(a, b, (n + 1) >> 1);
	lim = 1, l = 0;
	while (lim < (n << 1))
        lim <<= 1, l++;
    for (int i = 0; i < lim; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    for (int i = 0; i < n; i++)
    	tmp[i] = a[i];
    for (int i = n; i < lim; i++)
    	tmp[i] = 0;
    NTT(tmp, 1);
    NTT(b, 1);
    for (int i = 0; i < lim; i++)
        b[i] = ((2 - b[i] * tmp[i]) % mod + mod) % mod * b[i] % mod;
    NTT(b, -1);
    for (int i = n; i < lim; i++)
    	b[i] = 0;
}
void der(int *a, int *tar, int n){
	tar[n - 1] = 0;
	for (int i = 1; i < n; i++)
		tar[i - 1] = a[i] * i % mod;
}
void ining(int *a, int *tar, int n){
	tar[0] = 0;
	for (int i = 1; i < n; i++)
		tar[i] = a[i - 1] * qpow(i, mod - 2) % mod;
}
void gln(int *a, int *b, int n){
	der(a, tmp3, n);
	polyInv(a, tmp2, n);
	lim = 1, l = 0;
	while (lim <= n)
        lim <<= 1, l++;
    for (int i = 0; i < lim; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    NTT(tmp3, 1);
    NTT(tmp2, 1);
    for (int i = 0; i < lim; i++)
    	tmp3[i] = tmp3[i] * tmp2[i] % mod;
    NTT(tmp3, -1);
    ining(tmp3, b, n);
}
void polyln(int *a, int *b, int n){
	int LIM = 1;
	while (LIM <= n)
		LIM <<= 1;
	gln(a, b, LIM);
}
void polyexp(int *a, int *b, int n){
	if (n == 1){
		b[0] = 1;
		return;
	}
	polyexp(a, b, (n + 1) >> 1);
	polyln(b, tmp4, n);
	lim = 1, l = 0;
	while (lim < (n << 1))
        lim <<= 1, l++;
    for (int i = 0; i < lim; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    for (int i = 0; i < n; i++)
    	tmp4[i] = ((a[i] - tmp4[i]) % mod + mod) % mod;
    tmp4[0]++;
    for (int i = n; i < lim; i++)
    	tmp4[i] = b[i] = 0;
    NTT(tmp4, 1);
    NTT(b, 1);
    for (int i = 0; i < lim; i++)
        b[i] = b[i] * tmp4[i] % mod;
    NTT(b, -1);
    for (int i = n; i < lim; i++)
    	b[i] = 0;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    	cin >> a[i];
    polyexp(a, b, n);
    for (int i = 0; i < n; i++)
    	cout << b[i] << " ";
    return 0;
}
2024/12/17 07:51
加载中...