P9838 挑战 NPC IV

传送门

description

一个长度为 \(n\) 的排列的权值定义为其每个子区间内所有数 \(\text{lowbit}+1\) 之和（注意此处的 \(\text{lowbit}\) 表示二进制下最小的 1 在第几位，例如 \(\text{lowbit}(5)+1=1\)）。求所有长度为 \(n\) 的排列中权值第 \(k\) 小的排列的权值。

• \(n\leq 10^{18}\)

• \(k\leq \min(n!,10^{18})\)

solution

先把权值转化一下，考虑每个位置上数的贡献，排列 \(p\) 的权值就是 \(\sum\limits_{i=1}^n \text{lowbit}(p_i)\times(n-i+1)\times i\)。

设 \(w_i=(n-i+1)\times i\)，则 \(i\) 越接近 \(\dfrac{n}{2}\)，\(w_i\) 越大。所以我们把 \(\text{lowbit}\) 小的数尽量填到中间会让权值更小。

由于所有 \(\text{lowbit}\) 相同的数对权值的贡献都是一样的，所以权值最小的排列数量应该不低于 \(\prod\limits_{k\ge 1} cnt_k!\)，其中 \(cnt_k\) 表示 \(1\) 到 \(n\) 中，\(\text{lowbit+1}\) 为 \(k\) 的数的数量。显然这个东西的数量级非常大，而且这是个保守的下界，这说明当 \(n\) 比较大的时候，权值为所有排列中最小的的排列非常多。

有了上面的分析，再来看这个题。

\(n\) 非常大，但是 \(k\) 有上界 \(\min(n!,10^{18})\) 而不是 \(n!\)，结合上面的分析的结果，当 \(n\) 大于一个不是太大的常数的时候，对于 \(10^{18}\) 以内的所有 \(k\)，第 \(k\) 小排列的权值就等于权值最小的排列的权值。实际打表发现 \(n>28\) 时就可以全部取最小的可能的权值。

于是这个问题分成了两部分：

• 对 \(n\leq 28\)，求出答案

• 对 \(n>28\)，求出可能的权值最小的排列的权值。

第二个问题我们可以根据上面分析的贪心填法推式子计算出来最小权值，不是很难，就不写了。

第一个问题重点来看一看。由于要求第 \(k\) 小，所以我们要统计权值为 \(x\) 的方案数，从小到大，找到 \(k\) 所属的范围即可。

一个容易观察到的性质是：答案不超过 \(O(n^3\log n)\)。实际可以贪心地测出 \(28\) 以内的答案上界，为 \(5962\)。

所以可以设计出状态 \(f_{i,j,msk}\)，表示考虑前 \(i\) 个位置，总权值是 \(j\)，\(msk\) 是个长度为 \(n\) 的二进制数，表示每个数是否被填过，满足这些条件的方案数。可以 \(O(n)\) 转移。

这样的状态数非常大，不能接受。

又发现每个 \(\text{lowbit}\) 相同的数都是等效的，所以可以简化状态为 \(f_{i,j,msk}\)，前两维含义相同，最后一维的 \(msk\) 是一个长度为 \(O(\log n)\) 的二进制数，第 \(i\) 位表示 \(\text{lowbit}\) 为 \(i\) 的数用了几个的方案数，转移的时候多乘个 \(msk_i\) 就好。记忆化搜索实现，搜出来状态只有约 \(4\times 10^6\) 个，理论上是可以通过本题的。

具体实现的时候，dp 数组有个第一维，不好开成静态数组。可以发现 \(i=\sum msk_k\)。所以可以把第一维直接缩掉。

比赛的时候脑抽写的 map，被卡到比暴力还低。

code

#include<bits/stdc++.h>

using namespace std;

using E=long long;
constexpr E inf=1e18,mod=998244353;

E dp[5988][3601];
vector<vector<pair<int,pair<int,int>>>> ver;
vector<int> pw;

E dfs(E L,E n,E m,E msk){
  if(m-n<0) return 0;
  if(dp[m][msk]!=-1) return dp[m][msk];
  auto &x=dp[m][msk];
  x=0;
  if(n==0){
    if(m==0){
      return x=1;
    }
    return x=0;
  }
  for(auto j:ver[msk]){
    int p=j.first,w=j.second.first;
    E ret=dfs(L,n-1,m-w*(n*(L-n+1)),p);
    if(ret>=inf/j.second.second){
      x=inf;
      break;
    }
    ret*=j.second.second;
    x+=ret;
    if(x>=inf){
      x=inf;
      break;
    }
  }
  return x;
}

// 记录一下每个 n 的答案下界。
const int mina[]={0,1,6,13,32,50,84,117,188,242,330,408,550,658,824,965,1236,1418,1688,1912,2290,2563,2960,3284,3858,4242,4792,5236,5962,6474,7200};

// 建出状压后的图
void initVer(int dep,const vector<int> &msk,int now,int bs){
  if(dep==msk.size()){
    for(int i=0; i<msk.size(); i++){
      if((now/pw[i])%(1+msk[i])==0) continue;
      // cout<<"connect "<<now<<' '<<now-pw[i]<<endl;
      ver[now].emplace_back(make_pair(now-pw[i],make_pair(i+1,(now/pw[i])%(msk[i]+1))));
    }
    return ;
  }
  for(int i=0; i<=msk[dep]; i++){
    initVer(dep+1,msk,now+bs*i,bs*(msk[dep]+1));
  }
}

constexpr E inv6=166374059,inv2=(mod+1)>>1;
E S(E n){ n%=mod; return (n*(n+1)/2)%mod; }
E S2(E n){ n%=mod; return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;}
E F(E n,E i){ n%=mod,i%=mod; return (2*n-2*(i-1))*i%mod*inv2%mod; }

inline E getS(E n,E l,E r){
  E ret=0;
  if(l%2==0) ret=(ret+F(n,(l+1)/2))%mod,l++;
  if(r%2) ret=(ret+F(n,(r+1)/2))%mod,r--;
  if(l>r) return (ret%mod+mod)%mod;
  l=(l+1)/2,r=(r+1)/2;

  E sum=(2*n+2)%mod*(S(r)-S(l-1)+mod)%mod;
  sum=sum-2*(S2(r)-S2(l-1)+mod)%mod;
  sum%=mod;
  ret=(ret+sum)%mod;
  return (ret%mod+mod)%mod;
}

E getmin(E n){
  E ans=0;
  vector<pair<E,E>> val;
  for(int i=62; ~i; i--){
    if(n>>i&1){
      val.emplace_back(make_pair(i,(n>>(i+1))+1));
    }
    else val.emplace_back(make_pair(i,(n>>(i+1))));
  }
  sort(val.begin(),val.end());
  reverse(val.begin(),val.end());
  // for(auto pt:val) cout<<pt.first<<' '<<pt.second<<endl;

  E l=1,r;
  for(int t=0; t<val.size(); t++,l=r+1){
    E u=val[t].second;
    r=l+u-1;
    // cout<<"range "<<l<<' '<<r<<' '<<val[t].first+1<<' '<<getS(n,l,r)<<endl;
    ans=(ans+getS(n,l,r)*(val[t].first+1)%mod)%mod;
  }
  return ans;
}

int main(){

  int T;
  cin>>T;
  while(T--){
    E n,k;
    cin>>n>>k;
    ver.clear();
    if(n>28||(n>=20&&k<=10000000)){
      cout<<getmin(n)<<endl;
      continue;
    }
    memset(dp,-1,sizeof dp);
    vector<int> msk(n);
    for(int i=1; i<=n; i++){
      msk[__lg(i&-i)]++;
    }
    while(msk.size()&&msk.back()==0) msk.pop_back();
    E sz=1;
    for(auto pt:msk) sz=sz*(pt+1);
    pw.resize(msk.size()+1);
    pw[0]=1;
    for(int i=0; i<msk.size(); i++) pw[i+1]=pw[i]*(msk[i]+1);
    ver.resize(sz+1);
    initVer(0,msk,0,1);
    //cerr<<"mask size "<<sz<<endl;
    for(int i=mina[n]; i<=n*n*n; i++){
      E u=0;
      u=dfs(n,n,i,sz-1);
      // if(u) cout<<"getval "<<i<<' '<<u<<endl;
      if(k<=u){
        cout<<i%mod<<endl;
        break;
      }
      k-=u;
      //cerr<<"DP size: "<<dp.size()<<endl;
    }
    //cerr<<"DP size: "<<dp.size()<<endl;
  }

  return 0;
}