C++(g++ 7.5.0) 解法, 执行用时: 206ms, 内存消耗: 11928K, 提交时间: 2022-09-19 12:58:11

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1 << 19, mod = 167772161;
ll qsm(ll a, ll b) {
    ll s = 1;
    while (b) {
        if (b & 1) s = s * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return s;
}
void change(ll y[], int len) {
    int k;
    for (int i = 1, j = len / 2; i < len - 1; i++) {
        if (i < j) std::swap(y[i], y[j]);
        k = len / 2;
        while (j >= k) {
            j = j - k;
            k = k / 2;
        }
        if (j < k) j += k;
    }
}
// on == 1 时是 DFT，on == -1 时是 IDFT
void NTT(ll y[], int len, int on) {
    change(y, len);
    for (int h = 2; h <= len; h <<= 1) {
        ll wn = qsm(3, (mod - 1) / h);
        if (on == -1) wn = qsm(wn, mod - 2);
        for (int j = 0; j < len; j += h) {
            ll w = 1;
            for (int k = j; k < j + h / 2; k++) {
                ll u = y[k];
                ll t = w * y[k + h / 2] % mod;
                y[k] = (u + t) % mod;
                y[k + h / 2] = (u - t % mod + mod) % mod;
                w = w * wn % mod;
            }
        }
    }
    if (on == -1) {
        ll inv_n = qsm(len, mod - 2);
        for (int i = 0; i < len; i++) {
            y[i] = y[i] * inv_n % mod;
        }
    }
}
ll f[N], g[N], fac_inv[N];
int main() {
    int n;
    scanf("%d", &n);
    ll s = 1;
    fac_inv[0] = 1;
    for (int i = 1; i <= n; i++) fac_inv[i] = fac_inv[i - 1] * i % mod;
    fac_inv[n] = qsm(fac_inv[n], mod - 2);
    for (int i = n - 1; i >= 1; i--) fac_inv[i] = fac_inv[i + 1] * (i + 1) % mod;
    for (int i = 0; i <= n; i++) {
        g[i] = fac_inv[i];
        if (i & 1) g[i] = mod - g[i];
    }
    for (int i = 0; i <= n; i++) f[i] = qsm(i, n) * fac_inv[i] % mod;
    int lim = 1;
    while (lim <= 2 * n) lim <<= 1;
    NTT(f, lim, 1), NTT(g, lim, 1);
    for (int i = 0; i < lim; i++) f[i] = f[i] * g[i] % mod;
    NTT(f, lim, -1);
    for (int i = 0; i <= n; i++) {
        if (i) printf(" ");
        printf("%lld", f[i]);
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 175ms, 内存消耗: 21776K, 提交时间: 2023-08-11 12:30:21

#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int N=6e5+10,mod=167772161,G=3;
int a[N],b[N],g[N];
int rev[N];
int fac[N],inv[N];
int qz(int x,int y){
	int res=1;
	for(;y;y>>=1){
		if(y&1) res=res*x%mod;
		x=x*x%mod;
	}
	return res;
}
void init(int n){
	int i;
	fac[0]=1;
	For(i,1,n) fac[i]=fac[i-1]*i%mod;
	inv[n]=qz(fac[n],mod-2);
	FOR(i,n-1,0) inv[i]=inv[i+1]*(i+1)%mod;
}
void ntt(int a[],int sign,int tot){
	int i,j,mid;
	For(i,0,tot-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
	int inv_G=qz(G,mod-2);
	for(mid=1;mid<tot;mid<<=1){
		auto g1=qz(G,(mod-1)/(mid<<1));
		if(sign==-1) g1=qz(inv_G,(mod-1)/(mid<<1));
		for(i=0;i<tot;i+=(mid<<1)){
			auto gk=1; 
			for(j=0;j<mid;j++,gk=gk*g1%mod){
				auto x=a[i+j],y=gk*a[i+j+mid]%mod;
				a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;
			}
		}
	}
	int inv=qz(tot,mod-2);
	if(sign==-1) For(i,0,tot-1) a[i]=a[i]*inv%mod;
}
void mul(int a[],int n,int b[],int m,int c[]){
	int i,tot=0,bit=0;
	while((1<<bit)<=n+m) bit++;
	tot=1<<bit;
	For(i,0,tot-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	ntt(a,1,tot),ntt(b,1,tot);
	For(i,0,tot-1) c[i]=a[i]*b[i]%mod;
	ntt(c,-1,tot);
}
signed main(){
	init(2e5);
	int i,n;
	cin>>n;
	For(i,0,n){
		if(i&1) a[i]=-inv[i];
		else a[i]=inv[i];
	}
	For(i,0,n) b[i]=qz(i,n)*inv[i]%mod;
	mul(a,n+1,b,n+1,g);
	For(i,0,n) cout<<g[i]<<' ';
	cout<<'\n';
	return 0;
}