hdu_5322 Hope

题目:

  Hope is a good thing, which can help you conquer obstacles in your life, just keep fighting, and solve the problem below.
  In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting. These differ from combinations, which are selections of some members of a set where order is disregarded. For example, written as tuples, there are six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These are all the possible orderings of this three element set. As another example, an anagram of a word, all of whose letters are different, is a permutation of its letters. In this example, the letters are already ordered in the original word and the anagram is a reordering of the letters.
  There is a permutation , now we define its value as below:
  For each , if there exists a minimum j satisfies and , then connect an edge between and , so after we connect all the edges, there is a graph G, calculate the product of the number of nodes in each component as an integer P. The permutation value is P * P.Now, Mr. Zstu wants to know the sum of all the permutation value of n. In case the answer is very big, please output the answer mod .

思路:

  每个点会和它后面大于它的最近的点相连。这样的话,最大的点就不会再去连接别的点了。所以每次考虑把第 个点插入到 的排列中,假设插入位置为 ,那么 就和 分开了,且 中的所有点都连在一起了。那么dp转移就是:
  
  但是直接转移这个式子是 的。发现转移式中能提出 ,试着用多项式优化转移。转移时要求在计算 时, 已经完成计算。所以要在外面再套一层分治,复杂度:

代码:

#include <bits/stdc++.h>
#define _(...) (void)(__VA_ARGS__)
#define mset(a,b) memset(a,b,sizeof a)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
const int MOD=998244353;
const int N=262144+5;
typedef long long ll;

namespace NTT{
    int qkpow(int a,int k){
        int ans=1;
        for(;k;k>>=1,a=(ll)a*a%MOD)
            if(k&1)ans=(ll)ans*a%MOD;
        return ans;
    }
    int inv(int x){return qkpow(x,MOD-2);}
    int rev[N];
    void DFT(int a[],int n,bool inv_f){
        rep(i,0,n-1)
            if(i<rev[i])
                std::swap(a[i],a[rev[i]]);
        for(int l=2,m=1;l<=n;l<<=1,m<<=1){
            int base=qkpow(3,(MOD-1)/l);
            if(inv_f)base=inv(base);
            for(int *p=a;p!=a+n;p+=l){
                int w=1;
                rep(i,0,m-1){
                    int t=(ll)w*p[i+m]%MOD;
                    p[i+m]=(p[i]-t+MOD)%MOD;
                    p[i]=(p[i]+t)%MOD;
                    w=(ll)w*base%MOD;
                }
            }
        }
        int inv_n=inv(n);
        if(inv_f)rep(i,0,n-1)a[i]=(ll)a[i]*inv_n%MOD;
    }
    int log2(int x){
        int r=0;
        while((1<<r)<x)r++;
        return r;
    }
    int a[N],b[N];
    void calc(int _a[],int _b[],int res[],int n,int m){
        int lim=log2(n+m),r=1<<lim;
        rep(i,0,r-1)a[i]=b[i]=0;
        rep(i,0,n-1)a[i]=_a[i];
        rep(i,0,m-1)b[i]=_b[i];
        rep(i,0,r-1)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lim-1));
        DFT(a,r,false);DFT(b,r,false);
        rep(i,0,r-1)a[i]=(ll)a[i]*b[i]%MOD;
        DFT(a,r,true);
        rep(i,0,n+m-2)res[i]=a[i];
    }
}

int a[N],b[N],dp[N],res[N*2];
int fac[N],ifac[N];
void CDQ(int l,int r){
    if(l==r)return _(dp[l]=(ll)dp[l]*(l?fac[l-1]:1)%MOD);
    int mid=l+r>>1;
    CDQ(l,mid);
    rep(i,l,mid)a[i-l]=(ll)dp[i]*ifac[i]%MOD;
    rep(i,0,r-l)b[i]=(ll)i*i%MOD;
    NTT::calc(a,b,res,mid-l+1,r-l+1);
    rep(i,mid+1,r)(dp[i]+=res[i-l])%=MOD;
    CDQ(mid+1,r);
}

void init(){
    int n=1e5;
    fac[0]=1;
    rep(i,1,n)fac[i]=(ll)fac[i-1]*i%MOD;
    ifac[n]=NTT::inv(fac[n]);
    drep(i,n-1,0)ifac[i]=(ll)ifac[i+1]*(i+1)%MOD;
    dp[0]=1;
    CDQ(0,n);
}

int main(){
    int n;
    init();
    while(~scanf("%d",&n))
        printf("%d\n",dp[n]);
    return 0;
}