AtCoder - arc086_d Shift and Decrement分析与实现
分析与思路
可以把操作流程表示成下图
以进行四次除法操作为例：
这里有一个关键点：对于每个p_i (0<= i <=x-1) ，x是除法操作的次数，如果p_i>=2，可以将2个p_i的减法操作去掉，在p_(i+1)中增加一个减法操作，这样可以用更少的减法操作次数达到同样的效果，所以最终，每个p_i (0<= i <=x-1)，p_i要么是0，要么是1，p_x中保存了自底向上累计的减法，所以p_x取值任意
还可以继续简化操作，p_i (0<=i<=x-1)如果是1的话，可以将其去除，并让p_0增加2的 i 次方，此时虽然简化了操作，但是会增加操作次数
如果现在把操作次数统计为p_0+x+p_x，这样会用更多的次数完成相同的操作，这里有一个关键点，根据上面的p_0被累加的方式，p_0的二进制表达中1的个数是真实的p_0到p_(x-1)的操作次数的和，例如p_0 = 11011010，这代表着在p_0被增加前，p_0=0 p_1=1 p_2=0 p_3=1等等
这样，操作被简化为：
第一步：先进行p_0次减法操作，这里令y=p_0
第二步：再进行x次除法操作，
第三步：最后再进行p_x次减法操作，这里令z=p_x
操作次数为：y的二进制表达中1的出现次数+x+z
然后这里有一个关键观察，y的值不会超过2^x，就算y的二进制表达每一位都是1，也比2^x小1，于是可以将a_i表示成 a_i = b_i * 2^x + c_i，其中 0<=c_i<2^x，因为这样表示之后，
如果c_i>=y 则 经过前两步的操作，a_i变成b_i
如果c_i<y，则经过前两步的操作 a_i变成b_i - 1
将所有的c_i排序，去重，则当y处于以下的某一区间时，得到的前两步操作后的结果序列是相同的
[0,c1]
[c1+1,c2]
[c2+1,c3]
... ...
[c_(t-1) + 1, c_t] 其中 t 是c_i排序去重后的数的个数
当p处于某一区间时，为让所需操作次数减少，应该让p的二进制表达中1的个数尽量少（求一个区间[a,b]中的数的二进制表达中1的数目最少的数的方法见后）
现在，思路可以是，枚举x，因为指数爆炸，x的范围是[0,60]，然后枚举y，具体方式是对每个区间求二进制表达中1的个数最少的数就是这个区间的y，然后计算经过前两步操作后得到的数的序列，同时也根据k和前两步操作的次数，计算出第三步操作可以实施的次数，第三步操作其实是在整体移动这个数列
这里有一个关键点，用一个数组可以描述一个数列（长度为n）的形状，这个数组中的每个元素依次是：
a[1]-a[1] a[2]-a[1] a[3]-a[1] ... a[n]-a[1]
当数列的形状相同时，只要看a[1]有多少个不同的取值，就知道这个数列有多少不同的取值情况
记录每个数列的形状下，a[1]有多少个不同取值就可以
我们的算法在枚举前两步后，可以得到第三步的一个操作数量范围，这对应着某个形状下，一个a[1]的取值范围，a[1]的取值范围们的并集就是能取到的a[1]的值，这个并集中元素的数量就是这种形状下不同序列的数量
求区间[a,b]中二进制表达中1的数目最小的数的方法
设一个数p的二进制表达中1的数目为popcount(p)
求(a , b]中的答案可以用这样的方法，从高位到低位一位一位对比a和b，如果该位相同，则结果的该位和该位上的值相同，如果该位不同，则说明a的该位上是0，b的该位上是1，那么让结果的该位为1，后面的所有位置置0就可以
将[a,b]转化为(a-1,b]使用上述算法即可，但是有一个特殊情况，如果[a,b]中a是0，那么不能用上面的方法，应该直接返回结果0
合并区间的方法
记每个区间[l,r]
将区间按照左端点大小进行排序，记录当前已经处理到的位置的下一个位置为L，
分类讨论：如果一个区间的右端点小于L，那么不处理这个区间，否则，如果这个区间的左端点小于等于L，则区间带来的贡献是r-L+1，之后L=r+1，如果这个区间的左端点大于L，则区间带来的贡献是r-l+1，之后L=r+1
实现中的注意点
如果1<<60，会导致溢出，要写成1LL<<60
可以用map<vector<ll>,ll> 来表示某一种形状的序号，用tot表示当前形状的总数，如果当前形状的序号是0，那么当前形状的序号被编为tot+1
复杂度分析略
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=200+5,mod=1000000007;
ll power[maxn],a[maxn],b[maxn],c[maxn],fnal[maxn],c1[maxn];
ll k,n,tot;
map<vector<ll>,ll> mp;
vector<pair<ll,ll>> range[maxn*100];
ll find_minpopcount(ll x,ll y){
if(x==-1) return 0;
ll ans=0;
for(ll i=60;i>=0;i--){
if((x&(1LL<<i))==0 && (y&(1LL<<i))){
ans+=(1LL<<i);
break;
}
if(x&(1LL<<i)) ans+=(1LL<<i);
}
return ans;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
//预处理2的x次方
power[0]=1;
for(ll i=1;i<=60;i++) power[i]=power[i-1]*2;
//cout<<power[59]<<"\n";
//cout<<power[60]<<"\n";
//cout<<find_minpopcount(4,6)<<"\n";
cin>>n>>k;
for(ll i=1;i<=n;i++) cin>>a[i];
for(ll x=0;x<=60;x++){
for(ll i=1;i<=n;i++){
b[i]=a[i]/power[x];
c[i]=a[i]%power[x];
c1[i]=c[i];
}
stable_sort(c1+1,c1+1+n);
ll t=unique(c1+1,c1+1+n)-(c1+1);
c1[0]=-1;
for(ll i=1;i<=t;i++){
ll y=find_minpopcount(c1[i-1],c1[i]);
ll cnt=__builtin_popcountll(y);
ll flag=1;
for(ll j=1;j<=n;j++){
fnal[j]=b[j];
if(c[j]<y) fnal[j]--;
if(fnal[j]<0) {
flag=0;break;
}
}
if(flag==0) continue;
ll z=k-x-cnt;
if(z<0) {
continue;
}
/*
cout<<"发现合法结果："<<"\n";
printf("x=%d cnt=%d\n",x,cnt);
for(ll i=1;i<=n;i++) cout<<fnal[i]<<" ";
cout<<"\n";
*/
ll minfnal=*min_element(fnal+1,fnal+1+n);
ll max_decrease_times=min(minfnal,z);
pair<ll,ll> p={max(fnal[1]-max_decrease_times,0LL),fnal[1]};
//求差分模式
vector<ll> vec;
for(ll j=1;j<=n;j++){
vec.push_back(fnal[j]-fnal[1]);
}
if(mp[vec]==0) {
mp[vec]=++tot;
}
range[mp[vec]].push_back(p);
}
}
ll ans=0;
for(ll i=1;i<=tot;i++){
//printf("第%lld种差分模式：\n",i);
stable_sort(range[i].begin(),range[i].end());
ll L=0;
for(ll j=0;j<range[i].size();j++){
pair<ll,ll> tmp=range[i][j];
ll l=tmp.first,r=tmp.second;
//printf("区间：[%lld , %lld]\n",l,r);
if(r<L) continue;
if(l<=L) ans=(ans+(r-L+1))%mod;
else ans=(ans+(r-l+1))%mod;
L=r+1;
}
}
cout<<(ans+mod)%mod<<"\n";
return 0;
}