题解：P8340 [AHOI2022] 山河重整

· · 题解

My Blogs

P8340 [AHOI2022] 山河重整

题目限制是，对于一种选法 a，要求 \forall x,\sum_{a_i\leq x}a_i\geq x。所以有暴力 DP f_{i,j} 表示考虑了 \leq i 的所有数，和是 j。复杂度 \mathcal O(n^2)。

考虑优化，首先两维的状态就爆了。进行容斥，f_i 表示 \sum_{a_j\leq i}a_j=i，并且 \leq i 的数全部合法的方案数，答案就是 2^n-\sum_i f_i2^{n-i-1}，表示钦定 i+1 不合法，对第一次不合法的位置进行容斥。

考虑如何求 f，先设 g_i 表示 i 的互异分拆数。考虑把分拆数化成柱形图，一组拆分数 \sum b_i=n 表示为横坐标为 i 的格子上有一个高度为 b_i 的主子。因为是互异的，所以数字个数是 \mathcal O(\sqrt n) 的，也就是柱状图的宽度是 \mathcal O(\sqrt n) 的。枚举最大宽度，因为要求互异，所以比他小的每一种宽度都需要至少有一行，所以从大到小枚举宽度转移 g 就行了。

再考虑 f 的转移：f_i=g_i-\sum_{j<i}f_jval(j,i-j)，val(j,v) 表示用 \geq j+2 的数凑出来 v 的方案数。

这个不太好算，我们把所有的 j 放到一起算。这个转移显然有 i\geq 2j，所以进行一个牛顿迭代（？）。假设已经知道了 f_{\leq n}，考虑如何推出 f_{\leq 2n}。

注意到上面的转移天然可以对最小值进行限制。仍然是从大到小枚举宽度，假设枚举到宽度为 t 的，可以选择在 h 中加入一个 -f_j 的贡献：贡献到 j+(j+2)t 的位置上，表示最小值需要大于等于 j+2，其余 h 的转移和 g 相同，最后 f_i=g_i-h_i 即可。复杂度 T(n)=T(n/2)+\mathcal O(n\sqrt n)=\mathcal O(n\sqrt n)。

    int n,MOD;
    int g[500010],f[500010],h[500010];
    const int B=999;
    inline void solve(int n)
    {
        for(int i=0;i<=n;++i)h[i]=0;
        for(int i=B;i>=1;--i)
        {
            for(int j=0;j+i*(j+1)<=n;++j)
            Madd(h[j+i*(j+1)],f[j]);
            for(int j=n;j>=i;--j)h[j]=h[j-i];
            for(int j=0;j<i;++j)h[j]=0;
            for(int j=i;j<=n;++j)Madd(h[j],h[j-i]);
        }
        for(int i=n/2+1;i<=n;++i)f[i]=Cdel(g[i],h[i]);
    }
    inline void mian()
    {
        read(n,MOD);
        g[0]=1;
        for(int i=B;i>=1;--i)
        {
            for(int j=n;j>=i;--j)g[j]=g[j-i];
            for(int j=0;j<i;++j)g[j]=0;
            Madd(g[i],1);
            for(int j=i;j<=n;++j)Madd(g[j],g[j-i]);
        }
        int m=2;
        f[0]=f[1]=1;
        while(m<n)solve(m),m<<=1;
        solve(n);
        int ans=power(2,n);
        for(int i=0;i<n;++i)Mdel(ans,Cmul(f[i],power(2,n-i-1)));
        write(ans,'\n');
    }