P9838 [lg noip C] 挑战 NPC IV

· · 题解

Part 1. k=1

首先考虑 k=1 的时候怎么做。

考虑最终的位置 i 会被多少个区间统计到，不难发现它计入贡献的次数是 b_i=i(n-i+1)。
也就是说问题转化成，令 a_i=f(i)，b_i=i(n-i+1)，我们要对 a 序列指定一个顺序，最小化 \sum\limits_{i=1}^n a_i\times b_i。
这个问题有显然的贪心，a 序列升序排序，b 序列降序排序，对应位相乘即为最小值。证明是容易的：设 a<b 且 c<d，有 (b-a)d>(b-a)c，移项即得 ac+bd>ad+bc。

Part 2. n\in [29,10^6]

在上述过程中发现这么一个问题，方案本质不同的定义是 p 不相同，但 f(p_i) 中有很多数相同。交换它们中的一部分不会使贡献序列改变，但可以使 p 改变。因此我们估计，在不改变贡献序列的情况下，本质不同的 p 是相当多的。

考虑估计这个具体数目，a 序列中大约有 \frac{n}{2} 个 1，\frac{n}{2^2} 个 2（暂不讨论上下取整的问题），那么我们至少能搞出 cnt=\prod\limits_{i=1}^{\log_2 n} (\frac{n}{2^i})! 种取到最小值的排列。这里没考虑交换 b 序列的情况，因此实际值会比这更多。

这说明 k\le cnt 的时候答案都可以取到最小值。写个代码求上面的式子，可以发现 n=29 的时候 cnt 就超过了 10^{18}。也就是说，n>29 时 k 为任何值的答案都和 k=1 相等。

### Part 3. $n\in [29,10^{18}]

这一部分没有单独的部分分，但我们需要加速贪心的过程。
只要快速求出 a 序列中每个数的数量，就能找到它们在 b 序列中对应的连续区间。根据基础位运算知识可以得出值为 i 的出现次数。
令 s(l,r)=\sum\limits_{i=l}^r b_i，推式子：

\begin{aligned} s(l,r)&=\sum_{i=l}^r i(n-i+1)\\ &=(n+1)(\sum_{i=l}^r i)-\sum_{i=l}^r i^2\\ &=(n+1)\frac{(l+r)(r-l+1)}{2} - \frac{r(r+1)(2r+1)}{6}+\frac{l(l-1)(2l-1)}{6} \end{aligned}

现在这两个序列都能快速计算，我们可以在 O(\log n) 的时间复杂度内处理单次询问。

Part 4. n\le 28

看起来即使仅考虑本质不同的 a 序列，这样的数量依然很多。但是我们发现一条关键性质：这种情况下优美度的值域很小，只有 10^4 左右。
考虑基于这个进行 dp。进一步观察，a 序列中至多有 5 种不同的值。因为优美度已经计入了状态，我们显然只关心它们填了几个，而不关心它们的位置。

故设 f_{a,b,c,d,e,sum} 表示 1,2,3,4,5 分别填了 a,b,c,d,e 个，总优美度为 sum 的方案数。
转移时枚举当前位填什么数，式子是容易写出的。

这样的有效状态数在 n=28 时取到上界，大致有 16\times 9\times 5\times 3\times 2\times 1.1\times 10^4=4.752\times 10^7 种状态。开数组时请注意空间消耗。

结合 Part 3 的做法即可获得 100pts。

#define int long long
const int N=1e6+5,mod=998244353;
int T,n,k;
int f[16][9][5][3][2][11005];
int a[N],b[N],cnt[N],mx=11000,now[6],jc[N];
il int qpow(int n,int k=mod-2)
{
    int res=1;
    for(;k;n=n*n%mod,k>>=1) if(k&1) res=res*n%mod;
    return res;
}
il int S(int x) {x%=mod;return x*(x+1)%mod*(2*x+1)%mod*qpow(6)%mod;}
il int get(int l,int r,int n)
{
    if(l>r) return 0;
    if(r>n/2&&l<=n/2) return (get(l,n/2,n)+get(n/2+1,r,n))%mod; 
    if(l>n/2) l=n-l,r=n-r,swap(l,r);
    int res=n%mod*((l+r)%mod)%mod*((r-l+1)%mod)%mod*qpow(2)%mod-(S(r)-S(l-1)+mod)%mod;
    return (res%mod+mod)%mod;
}
il void solve(int n)
{
    int l=1,r=n,res=0;
    for(int i=__lg(n)+1;i;i--)
    {
        int sum=(n>>i)+(n>>(i-1)&1);
        int ls=sum/2,rs=sum-ls;
        if(l<n-r+1) swap(ls,rs);
        (res+=i*get(l,l+ls-1,n+1)%mod)%=mod,(res+=i*get(r-rs+1,r,n+1)%mod)%=mod;
        l+=ls,r-=rs;
    }
    printf("%lld\n",res);
}
signed main()
{
    T=read(); jc[0]=1;
    for(int i=1;i<=15;i++) jc[i]=jc[i-1]*i;
    while(T--)
    {
        n=read(),k=read();
        if(n>28) {solve(n);continue;}
        for(int i=1;i<=n;i++) a[i]=1+__lg(i&(-i));
        for(int i=1;i<=n;i++) b[i]=i*(n-i+1);
        sort(a+1,a+n+1),sort(b+1,b+n+1);
        for(int i=1;i<=n;i++) cnt[i]=0;
        for(int i=1;i<=n;i++) cnt[a[i]]++;
        int Cnt=1;
        if(n<=28) for(int i=1;i<=__lg(n)+1;i++) Cnt=Cnt*jc[cnt[i]];
        f[0][0][0][0][0][0]=1;
        for(now[1]=0;now[1]<=cnt[1];now[1]++)
        for(now[2]=0;now[2]<=cnt[2];now[2]++)
        for(now[3]=0;now[3]<=cnt[3];now[3]++)
        for(now[4]=0;now[4]<=cnt[4];now[4]++)
        for(now[5]=0;now[5]<=cnt[5];now[5]++)
        {
            int sum=0;
            for(int i=1;i<=5;i++) sum+=now[i];
            if(!sum) continue;
            for(int j=0;j<=mx;j++)
            {
                int i=0;
                for(int k=1;k<=5;k++)
                {
                    if(now[k]==0) continue;
                    if(j-k*b[sum]<0) continue;
                    now[k]--;
                    i+=f[now[1]][now[2]][now[3]][now[4]][now[5]][j-k*b[sum]];
                    now[k]++;
                }
                f[now[1]][now[2]][now[3]][now[4]][now[5]][j]=i;
            }
        }
        int ans=0;
        for(int i=0;i<=mx;i++)
        {
            ans+=Cnt*f[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][i];
            if(ans>=k) {printf("%lld\n",i);break;}
        }
    }
    return 0;
}