P3711 仓鼠的数学题

题意：

的答案多项式\(\sum_{i=0}^{n+1}c_ix^i\)各项系数

一开始用了\(B^-\)，然后后面要展开\((x+1)^k\)，完全不会做

和出题人fjzzq2002讨论了一下，原来标程用的是\(B^+\)，不需要展开了

那就很简单了...不想写过程了，最后的结果就是

然后我发现用\(B^+\)好像没有常数项啊？但是用\(B^-\)写暴力计算确实有常数项

然后发现常数项就是\(a_0\)，交上就过了...

update:去问了张队长，然后意识到，\(B^+\)算的和是从1开始...然后常数项就是\(a_0 0^0 = a_0\)

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N = (1<<20) + 5, P = 998244353, mo = P, inv2 = (P+1)/2;

const double PI = acos(-1.0);

inline int read(){

    char c=getchar(); int x=0,f=1;

    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}

    return x*f;

}

inline int Pow(ll a, int b) {

	ll ans = 1;

	for(; b; b>>=1, a=a*a%P)

		if(b&1) ans=ans*a%P;

	return ans;

}

namespace fft {

	int rev[N], g = 3;

	void dft(int *a, int n, int flag) {

		int k = 0; while((1<<k) < n) k++;

		for(int i=0; i<n; i++) {

			rev[i] = (rev[i>>1]>>1) | ((i&1)<<(k-1));

			if(i < rev[i]) swap(a[i], a[rev[i]]);

		}

		for(int l=2; l<=n; l<<=1) {

			int m = l>>1, wn = Pow(g, flag==1 ? (P-1)/l : P-1-(P-1)/l);

			for(int *p = a; p != a+n; p += l)

				for(int k=0, w=1; k<m; k++, w = (ll)w*wn %P) {

					int t = (ll) p[k+m] * w %P;

					p[k+m] = (p[k] - t + P) %P;

					p[k] = (p[k] + t) %P;

				}

		}

		if(flag == -1) {

			ll inv = Pow(n, P-2);

			for(int i=0; i<n; i++) a[i] = a[i] * inv %P;

		}

	}

	int t[N];

	void inverse(int *a, int *b, int l) {

		if(l == 1) {b[0] = Pow(a[0], P-2); return;}

		inverse(a, b, l>>1);

		int n = l<<1;

		for(int i=0; i<l; i++) t[i] = a[i], t[i+l] = 0;

		dft(t, n, 1); dft(b, n, 1);

		for(int i=0; i<n; i++) b[i] = (ll) b[i] * (2 - (ll) b[i] * t[i] %P + P) %P;

		dft(b, n, -1); for(int i=l; i<n; i++) b[i] = 0;

	}

	void mul(int *a, int *b, int n) {

		dft(a, n, 1); dft(b, n, 1);

		for(int i=0; i<n; i++) a[i] = (ll) a[i] * b[i] %P;

		dft(a, n, -1);

	}

}

int n, a[N], len;

ll inv[N], fac[N], facInv[N];

int q[N], b[N], f[N], g[N];

int main() {

	freopen("in", "r", stdin);

	n=read();

	for(int i=0; i<=n; i++) a[i] = read();

	inv[1] = fac[0] = facInv[0] = 1;

	for(int i=1; i<=n+2; i++) {

		if(i != 1) inv[i] = (P - P/i) * inv[P%i] %P;

		fac[i] = fac[i-1] * i %P;

		facInv[i] = facInv[i-1] * inv[i] %P;

	}

	len = 1; while(len <= n+1) len <<= 1;

	for(int i=0; i<=n+1; i++) q[i] = facInv[i+1];

	fft::inverse(q, b, len);

	for(int i=0; i<=n+1; i++) b[i] = b[i] * fac[i] %P;

	b[1] = inv2;

	for(int i=0; i<=n; i++) f[i] = (ll) a[i] * fac[i] %P;

	for(int i=0; i<=n; i++) g[n+1-i] = (ll) b[i] * facInv[i] %P;

	while(len <= n+n+1) len <<= 1;

	fft::mul(f, g, len);

	printf("%d ", a[0]);

	for(int i=1; i<=n+1; i++) printf("%lld ", f[n+i] * facInv[i] %P);

}