星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

HDU5322 Hope(CDQ+NTT/前缀和)

posted on 2018-05-24 19:00:48 | under 题解 |

给出一个排列,每个点向它右面离它最近的且比它大的点连无向边,每个连通块的价值为这个连通块大小的平方,每个排列的价值为所有连通块价值之积。求 $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)$ 维护组合数逆元/维护好逆元后直接作逆元的阶乘。

#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;
}