自动搬运

查看原文

来自洛谷，原作者为

	樱雪喵 无尽欺骗，无限祈愿 | AFOed | qq: 3480681868

搬运于2025-08-24 22:52:18，当前版本为作者最后更新于2023-11-11 19:45:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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$ 相等。

$O(n)$ 地模拟上述贪心，配合爆搜可以通过前 $13$ 个点。有 52pts 暴力分，好良心！

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