HDU5322 Hope(CDQ+NTT/前缀和)
teafrogsf
2018-05-24 19:00:48
### 给出一个排列，每个点向它右面离它最近的且比它大的点连无向边，每个连通块的价值为这个连通块大小的平方，每个排列的价值为所有连通块价值之积。求$n$个数的所有排列的价值之和。
感谢SilverNebula的题意。
这个题我们需要发现一个性质：当一个$1-i$的排列中$i$在$j$位置时，$i$会把它前面和后面分成两个部分，这是很显然的。
于是我们可以得到转移方程：
$$dp[i]=\sum_{j=1}^idp[i-j]A_{i-1}^{j-1}j^2$$
然后我们就有两种做法：
### 1.
$$dp[i]=(i-1)!\sum_{j=1}^ij^2\frac{dp[i-j]}{(i-j)!}$$
这后面是个卷积形式了。
但是我们发现不能直接用NTT加速，因为dp[i-j]的值每次是未确定的。
所以我们可以利用CDQ分治，每次单独考虑左边对右边的影响。总的时间复杂度是$O(n\log^2 n)$。
### 2.
$$dp[i]=(i-1)!\sum_{k=0}^{i-1}(i-k)^2\frac{dp[k]}{k!}$$
$$=(i-1)!\sum_{k=0}^{i-1}(i^2-2ik+k^2)\frac{dp[k]}{k!}$$
然后我们可以维护三个前缀和，直接算就可以了。
以上两种做法都可以利用$O(n)$维护组合数逆元/维护好逆元后直接作逆元的阶乘。
```cpp
#include<cstdio>
#include<ctime>
#include<algorithm>
#include<iostream>
#define neko 100010
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register long long i=(a);i<=(b);i=-(~(i)))
#define rf(i,a,b) for(register long long i=(a);i>=(b);i=~(-(i)))
typedef long long ll;
ll a[neko],b[neko],rev[neko],mod=998244353;
ll slowpow(ll m,ll n)
{
ll b;
for(b=1;n;n>>=1,m=m*m%mod)if(n&1)b=b*m%mod;
return b;
}
int n;
typedef ll arr[neko];
arr fac,dp,invfac;
void countans()
{
ll sum1,sum2,sum3;sum1=sum2=sum3=0;
f(i,0,100000)
{
if(!i)dp[i]=1;
else dp[i]=(fac[i-1]*((i*i%mod*sum1%mod-2ll*i*sum2%mod)%mod+sum3)%mod+mod)%mod;
sum1=(sum1+invfac[i]*dp[i]%mod)%mod;
sum2=((sum2+i*invfac[i]%mod*dp[i]%mod)%mod+mod)%mod;
sum3=(sum3+i*i%mod*invfac[i]%mod*dp[i]%mod)%mod;
}
}
int main()
{
fac[0]=invfac[0]=1;
f(i,1,100005)fac[i]=(fac[i-1]*i%mod+mod)%mod;
invfac[100005]=slowpow(fac[100005],mod-2);
rf(i,100004,1)invfac[i]=invfac[i+1]*(i+1)%mod;
countans();
while(~scanf("%d",&n))printf("%lld\n",dp[n]);
return 0;
}
```