校内作业多,一直忘记写blog
现在开始补上量
赛后几天秒掉了,场上真是困糊涂了,没想到分治
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define ll long long
#define node pair<int,pair<ll,ll>>
#define mp(x,y,z) make_pair(x,make_pair(y,z))
#define fi first
#define se second.first
#define th second.second
int t,k;
ll n;
map<pair<ll,int>,node> p;
node solve(ll n,int k){
if(p.count(make_pair(n,k)))return p[make_pair(n,k)];
if(k<0)return p[make_pair(n,k)]=mp(0,0LL,0LL);
if(n==1)return p[make_pair(n,k)]=mp(1,1LL,1LL);
// printf("%lld %d\n",n,k);
for(int m=62;m>=0;m--){
if((1LL<<m)<n){
node res1=solve(1LL<<m,k),res2=solve(n-(1LL<<m),k-1);
node res=mp((res1.fi+res2.fi)%mod,0,0);
if(res1.se==(1LL<<m))res.se=res1.se+res2.se;
else res.se=res1.se;
if(res2.th==n-(1LL<<m))res.th=res1.th+res2.th;
else res.th=res2.th;
res.fi=(res.fi+1LL*res1.th%mod*(res2.se%mod))%mod;
return p[make_pair(n,k)]=res;
}
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%lld%d",&n,&k);
printf("%d\n",solve(n,k).fi);
}
return 0;
}
附考场唐氏代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pli pair<ll,int>
#define mp make_pair
#define fi first
#define se second
#define It set<pair<ll,int>>::iterator
const int mod=1e9+7;
int ksm(int x,int y){
int res=1;
while(y){
if(y&1)res=1LL*res*x%mod;
x=1LL*x*x%mod;
y>>=1;
}
return res;
}
int T,k;
ll n,res;
set<pli> s[65];
int calc_min(ll l,ll r){
int sum=0,sum1=0;
for(int i=60;i>=0;i--)sum1+=(l>>i)&1;
for(int i=60;i>=0;i--){
int a=(l>>i)&1,b=(r>>i)&1;
if(a!=b){
if(i==0)return min(sum,sum1);
else return min(sum+1,sum1);
}
if(a==1)sum++;
}
return min(sum,sum1);
}
int calc_max(ll l,ll r){
int sum=0,sum1=0;
for(int i=60;i>=0;i--)sum1+=(r>>i)&1;
for(int i=60;i>=0;i--){
int a=(l>>i)&1,b=(r>>i)&1;
if(a!=b){
if(i==0)return max(sum+1,sum1);
else return max(sum+i,sum1);
}
if(a==1)sum++;
}
return max(sum,sum1);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%lld%d",&n,&k);
ll now=0;res=0;
s[k].insert(mp(n,0));
It it=s[k].find(mp(n,0));
if(it!=s[k].begin())now=(*prev(it)).fi+1,res=(*prev(it)).se;
s[k].erase(mp(n,0));
if(calc_max(now,now)>k){
ll l=now+1,r=n-1,fin=now;
while(l<=r){
ll mid=(l+r>>1);
if(calc_min(now,mid)>k)fin=mid,l=mid+1;
else r=mid-1;
}
now=fin+1;
}
while(now<n){
ll l=now+1,r=n-1,fin=now;
while(l<=r){
ll mid=(l+r>>1);
if(calc_max(now,mid)<=k)fin=mid,l=mid+1;
else r=mid-1;
}
ll len=fin-now+1;now=fin+1;
len%=mod;res+=len*(len+mod-1)%mod*ksm(2,mod-2);res%=mod;
res+=len;res%=mod;
if(fin!=n-1)s[k].insert(mp(now,res));
l=now+1,r=n-1,fin=now;
while(l<=r){
ll mid=(l+r>>1);
if(calc_min(now,mid)>k)fin=mid,l=mid+1;
else r=mid-1;
}
now=fin+1;
}
printf("%lld\n",res);
}
return 0;
}
标签:int,每日,sum1,CF1982E,sum,now,ll,define
From: https://www.cnblogs.com/kentsbk/p/18286712