题解：AT_arc220_e [ARC220E] popcount ≥ K

· · 题解

更好的阅读体验

我们需要解决这样一个问题：找到最小的，连续 n 个 \bmod \space c 同余的数字，使这些数字的 popcount 都 \ge k。

那么可以二分。假设目前位于区间 [l, r)，区间的中点是 mid。那么，

假设答案上界为 2^V。那么我们初始时 l = 0, r = 2^V，r-1 都是将 l 末尾若干个 0 填补成 1 的数。

由于 c 很小，我们对于每一个 c 分别处理这个问题。

我们假设 f_{i, j, k} 维护一个五元组 (len, pre, suf, mx, all)，分别表示 [0, 2^i) 所有 \bmod \space c = j 的数字个数，\bmod \space c = j 的数字中最长的前缀使每个数 popcount 都 \ge k，\bmod \space c = j 的数字中最长的后缀使每个数 popcount 都 \ge k，\bmod \space c = j 的数字中最长的子段使每个数 popcount 都 \ge k，以及是否所有 \bmod \space c = j 的数字 popcount 都 \ge k。

合并这样的两个五元组是简单的，在这里不再赘述。

首先假设我们已经求出了 f 数组，我们假设 g(l, i, j, k) 表示 [l, l+2^i) 中，\bmod \space c = j 且 popcount \ge k 的数的 (len, pre, suf, mx, all) 五元组。这里需要保证 l 的 lowbit 2^b 要大于 2^i。

那么有了这个我们同时可以解决 f 的转移问题。容易发现

f_{i+1, j, k} = \operatorname{merge}\left(f_{i, j, k}, g(2^i, i, j, k)\right)

由于此时 f_{i, *, *} 的值都是已知的，因此 g 能得到求解。

我们重新回到上述的二分过程。由于余数未知，我们可以首先枚举余数 x。容易发现，假设 r - l = 2^b，则我们只需要分别求出 g(l, b, x, k), g(l, b-1, x, k), g(mid, b-1, x, k)，就可以判定答案是出现在区间的什么位置了，最后对所有 x 的结果取 \min。

按照上述过程二分即可。

假设答案上界为 2^V。那么对于单个 c，预处理 f 数组的复杂度是 O(V^2 c)，单个询问二分和枚举余数的复杂度是 O(Vc)。综上，问题在 O(V^2c^2 + TVc) 的时间，O(V^2 c) 的空间内得到解决。

#include<bits/stdc++.h>
#define endl '\n'
#define N 100006
using namespace std;
using i64=long long;
int q; i64 ans[N];
struct Ask {int n,c,k;} ask[N];
struct Node {
  i64 len,pre,suf,mx; int all;
  Node():len(0),pre(0),suf(0),mx(0),all(1) {}
  void set() {len=pre=suf=mx=all=1;}
  friend Node operator +(Node x,Node y)
  {
    Node ret;
    ret.len=x.len+y.len,ret.all=x.all&y.all;
    ret.pre=x.all?x.len+y.pre:x.pre;
    ret.suf=y.all?x.suf+y.len:y.suf;
    ret.mx=max({x.mx,y.mx,x.suf+y.pre});
    return ret;
  }
} f[60][36][60];
i64 calc(i64 r,int c,int k) {return r<k?0:(r-k)/c+1;}
i64 calc(i64 l,i64 r,int c,int k) {return calc(r,c,k)-calc(l-1,c,k);}
i64 get(i64 r,i64 x,int c,int k) {return k+(r-k)/c*c-(x-1)*c;}
Node query(int c,i64 st,int i,int j,int k)
{
  i64 l=st,r=st+(1ll<<i)-1;
  int pc=__builtin_popcountll(st);
  if(!calc(l,r,c,j))return Node();
  if(pc>=k)
  {
    Node ret;
    ret.len=ret.pre=ret.suf=ret.mx=calc(l,r,c,j),ret.all=1;
    return ret;
  }
  return f[i][((j-st+c)%c+c)%c][k-pc];
}
main()
{
  scanf("%d",&q);
  for(int i=1;i<=q;i++)
    scanf("%d%d%d",&ask[i].n,&ask[i].c,&ask[i].k);
  for(int c=1;c<=30;c++)
  {
    for(int i=0;i<60;i++)
      for(int j=0;j<36;j++)
        for(int k=0;k<60;k++)f[i][j][k]=Node();
    for(int j=0;j<60;j++)
      f[0][0][j].len=1,f[0][0][j].all=0;
    f[0][0][0].set();
    for(int i=0;i<59;i++)
      for(int j=0;j<c;j++)
      {
        for(int k=0;k<=i+1;k++)
          f[i+1][j][k]=f[i][j][k]+query(c,1ll<<i,i,j,k);
        for(int k=i+2;k<60;k++)
        {
          f[i+1][j][k].len=calc(0,(1ll<<i+1)-1,c,j);
          if(f[i+1][j][k].len)f[i+1][j][k].all=0;
        }
      }
    for(int i=1;i<=q;i++)if(ask[i].c==c)
    {
      if(ask[i].n==1) {ans[i]=(1ll<<ask[i].k)-1; continue;}
      i64 l=0,r=1ll<<60,b=60;
      for(;;b--)
      {
        i64 mid=l+(1ll<<b-1);
        int flag=0;
        for(int x=0;x<c;x++)
          if(query(c,l,b-1,x,ask[i].k).mx>=ask[i].n)flag=1;
        if(flag) {r=mid; continue;}
        i64 res=2e18;
        for(int x=0;x<c;x++)
        {
          i64 l_suf=query(c,l,b-1,x,ask[i].k).suf;
          i64 r_pre=query(c,mid,b-1,x,ask[i].k).pre;
          if(l_suf+r_pre>=ask[i].n)
            flag=1,res=min(res,get(mid-1,l_suf,c,x));
        }
        if(flag) {ans[i]=res; break;}
        l=mid;
      }
    }
  }
  for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
  return 0;
}