【xsy2166】Hope cdq分治+NTT

题目 分治 FFT

---

题意

  对于 $1$ 到 $n$ 的一个排列 $a_1,a_2,...,a_n$ ，我们定义这个序列的P值和Q值；
  对于每个 $A_i$ ，如果存在一个最小的 $j$ ，使得 $i<j$ ，则将点 $i$ 与点 $j$ 连一条无向边。于是就得到了一幅图。计算这个图的连通块的大小，将它们相乘，得到 $P$ 。记 $Q=P^k$ 。
  求 $1$ 到 $n$ 的所有排列的Q值之和。

   $1\leq n,k\leq 10^5$

分析

  设 $f_n$ 表示 $1$ 到 $n$ 的所有排列的Q值之和，考虑如何求 $f_n$ 。
  我们用递推的方式求 $f_n$ 。枚举 $n$ 所在的位置为 $x$ ，则前 $x$ 个选择的方案数有 $\binom{n-1}{x-1}(x-1)!$ 个。贡献和为 $x^k\times f_{n-k}$ 。综上，得到

$$\begin{aligned}f_n&=\sum_{x=1}^n \binom{n-1}{x-1}(x-1)!x^kf_{n-k}\\&=\sum_{x=1}^n\frac{(n-1)!}{(x-1)!(n-x)!}(x-1)!x^kf_{n-x}\\&=(n-1)!\sum_{x=1}^nx^k\frac{f_{n-x}}{(n-x)!}\end{aligned}$$
$$\frac{f_n}{(n-1)!}=\sum_{x=1}^nx^k\frac{f_{n-x}}{(n-x)!}$$
  考虑使用分治+NTT解决。

实现

  在这道题中，我学会了一些NTT的新姿势——这样写常数小很多。
  姿势1： $O(n)$ 的简易交换。
F(i,0,n-1) rev[i]=rev[i>>1]>>1|(i&1)<<(bit-1)
  姿势2： wi[i],wiv[i] 表示 $G^{\frac{L-1}{1<<i}},invG^{\frac{L-1}{1<<i}}$ 。
  姿势3：空间开大4倍（因为 wi 和 wiv ）。
  更多的细节见代码。

#include <cstdio>
#include <iostream>
#include <cctype>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define LL long long
const int N=524288;
const int L=998244353;
const int G=3;
int n,k;
int b[N];
int inv[N];
int wi[N],wiv[N];
int rev[N];
int a[N];
int ans;
int pwr(int x,int y) {
    int mul=0;
    for (;y>0;y>>=1,x=(LL)x*x%L)
        if (y&1) mul=(LL)mul*x%L;
    return mul;
}
void NTT(int *a,int n,int bit,int kd) {
    F(i,0,n-1) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int i=2;i<=n;i<<=1) {
        int wn=(kd==1?wi[i]:wiv[i]);
        for (int j=0;j<n;j+=i) {
            int w=1;
            F(k,0,i/2-1) {
                int x=a[j+k],y=(LL)w*a[j+k+i/2]%L;
                a[j+k]=(x+y)%L,a[j+k+i/2]=((x-y)%L+L)%L;
                w=(LL)w*wn%L;
            }
        }
    }
    if (kd==-1) {
        int invn=pwr(n,L-2);
        F(i,0,n-1) a[i]=(LL)a[i]*invn%L;
    }
}
void Solve(int l,int r) {
    if (l==r) {
        if (!l) a[l]=1; else a[l]=(LL)a[l]*inv[l]%L;
        return;
    }
    int mid=(l+r)>>1;
    Solve(l,mid);
    int n1=mid-l+1,d1=l;
    int n2=r-l,d2=1;
    int dall=d1+d2;
    int len=1,bit=0;
    while (len<=(n1-1)+(n2-1)) len<<=1,bit++;
    F(i,0,len-1) rev[i]=rev[i>>1]>>1|(i&1)<<(bit-1);
    static int ta[N],tb[N];
    F(i,0,len-1) ta[i]=tb[i]=0;
    F(i,d1,mid) ta[i-d1]=a[i];
    F(i,d2,r-l) tb[i-d2]=b[i];
    NTT(ta,len,bit,1);
    NTT(tb,len,bit,1);
    F(i,0,len-1)
        ta[i]=(LL)ta[i]*tb[i]%L;
    NTT(ta,len,bit,-1);
    F(i,mid+1,r)
        a[i]=(a[i]+ta[i-dall])%L;
    Solve(mid+1,r);
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        freopen("sdchr.out","w",stdout);
    #endif
    cin>>n>>k;
    inv[1]=1; F(i,2,n) inv[i]=((LL)L-L/i)*inv[L%i]%L;
    F(i,0,n) b[i]=pwr(i,k);
    int bit=0,len=1;
    while (len<=n+n) bit++,len<<=1;
    int invG=pwr(G,L-2);
    F(i,0,bit) {
        wi[1<<i]=pwr(G,(L-1)/(1<<i));
        wiv[1<<i]=pwr(invG,(L-1)/(1<<i));
    }
    Solve(0,n);
    ans=a[n]; F(i,1,n) ans=(LL)ans*i%L; cout<<ans<<endl;
    return 0;
}