Submission #2241939

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;


int N,K;
int A[222];

signed main(){
    cin>>N>>K;
    rep(i,N)cin>>A[i];
    sort(A,A+N);
    map<vint,vpint>ei;

    for(int i=0;i<=60;i++){
        vint v(N);
        rep(j,N)v[j]=A[j]%(1ll<<i);
        sort(all(v));

        vpint lis;
        if(i<=K)lis.pb({0,K-i});
        for(int j=0;j+1<v.size();j++){
            if(v[j+1]==v[j])continue;
            int cnt=0;
            for(int k=60;k>=0;k--){
                if(v[j+1]>>k&1)cnt++;
                if((v[j+1]>>k&1)!=(v[j]>>k&1))break;
            }
            if(cnt+i>K)continue;
            lis.pb({v[j]+1,K-cnt-i});
        }

        for(auto p:lis){
            vint a(N);
            rep(j,N)a[j]=(A[j]-p.fi)>>i;
            vint d(N-1);
            rep(j,N-1)d[j]=a[j+1]-a[j];
            ei[d].pb({max(0ll,a[0]-p.se),a[0]+1});
        }
    }

    int ans=0;
    for(auto &p:ei){
        vpint v=p.se;

        sort(all(v));
        vpint u;
        for(auto &q:v){
            if(u.size()==0||u.back().se<q.fi)u.pb(q);
            else u.back().se=q.se;
        }
        for(auto &q:u)ans=(ans+q.se-q.fi)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result