题解 P7156 [USACO20DEC] Cowmistry P

题目大意:
给 个区间 ,问在所有区间的并中有多少个三元组 ,满足:
互不相同 . .输出对 取模。
数据范围: .
题目难度:NOI/NOI+/CTSC

解析:
没人写官方题解思路啊,那我写一手
首先对 这样就把 转化成了 。定义 为最小的 的次幂使得 ,那么显然 必须满足(否则会有 且不为 0 的位出现):
接下来分类讨论:

此时 在 以上的位均为 ,显然满足要求,统计相等的数量并对答案加上 即可。
其他情况由于 以上的二进制位值都一样,抽屉原理得出必有两项 满足 。不妨考虑 时的情况,由于显然有 ,只用考虑对每个 求所有满足 的 。
具体地,有 ,集合 为 所有 且 的 ,对于该 的答案就是 。
下面考虑如何实现,首先我们将每个原区间按上述讨论拆为长度为 的整块和不到 的散块。对于长度为 的块,答案为
接下来把散块离线处理,
void solve(vector <pii> v){
int p2=p/2;
vector<pii>tot[2];
for(auto& t:v){
if(t.fi/p2<t.se/p2){
tot[0].push_back({t.fi,p2-1});
tot[1].push_back({0,t.se-p2});
}else
tot[t.fi/p2].push_back({t.fi%p2,t.se%p2});
}
rep(i,0,1){
add(ans,c3(totlen(tot[i])));//第一类
solve2(tot[i],tot[i^1],p2,0);//第二类
}
}
第一类的答案很好统计,考虑如何处理第二类。可以将第二类划分为更小的两个区间进行计算,这样的分治最多进行 层,可以通过。
时间复杂度: .
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int M=1e9+7,i6=166666668;
int n,k,p=1;
ll ans;
ll c2(ll x){return 1ll*x*(x-1)/2%M;}
ll c3(ll x){return 1ll*x*(x-1)%M*(x-2)%M*i6%M;}
inline void add(ll &a,const ll b){a=(a+b)%M;}
inline ll totlen(const vector<pii>&v){
ll len=0;for(auto &t:v)len+=t.se-t.fi+1;
return len;
}
void solve2(const vector<pii>&a,const vector<pii>&b,int block,int cur){
//基本情况
if(!(int)a.size())return;
if(!(int)b.size()){
ans=(ans+c2(cur)*totlen(a)%M)%M;
return;
}
vector<pii> des{{0,block-1}};
if (b == des) { // b = [0,block)
cur =(cur+((block-1)&k))%M;
ans=(ans+c2(cur)*totlen(a)%M)%M;
return;
}
//继续往下分治
vector<pii> A[2], B[2];
auto ad = [&](vector<pii>& v,pii p) {
p.fi=max(p.fi,0),p.se=min(p.se,block/2-1);
if (p.fi > p.se) return;
v.push_back(p);
};
for (auto& t: a) ad(A[0],t), ad(A[1],{t.fi-block/2,t.se-block/2});
for (auto& t: b) ad(B[0],t), ad(B[1],{t.fi-block/2,t.se-block/2});
if (k&(block/2)) {
for(int i=0; i<2; ++i) solve2(A[i],B[i^1],block/2,(cur+totlen(B[i]))%M);
} else {
for(int i=0; i<2; ++i) solve2(A[i],B[i],block/2,cur);
}
}
//处理a/P相等的散块
void solve(vector <pii> v){
int p2=p/2;
vector<pii>tot[2];
for(auto& t:v){
if(t.fi/p2<t.se/p2){
tot[0].push_back({t.fi,p2-1});
tot[1].push_back({0,t.se-p2});
}else
tot[t.fi/p2].push_back({t.fi%p2,t.se%p2});
}
rep(i,0,1){
add(ans,c3(totlen(tot[i])));//第一类
solve2(tot[i],tot[i^1],p2,0);//第二类
}
}
int main(){
n=read(),k=read();
++k;while(p<=k)p<<=1;
k=k-p/2;
ll sum=(p*c2(k)%M+2*c3(p/2)%M)%M;//整块答案直接统计
map<int,vector<pii>>todo;
rep(i,1,n){
int l=read(),r=read();
int LL=l/p,RR=r/p;
if(LL!=RR){
add(ans,sum*(RR-LL-1)%M);
todo[LL].push_back({l%p,p-1});
todo[RR].push_back({0,r%p});
}else todo[LL].push_back({l%p,r%p});
}
for(auto& t:todo)solve(t.se);
printf("%lldn",ans%M);
return 0;
}

【竞赛报名/项目咨询请加微信:mollywei007】

微信扫一扫,分享到朋友圈

题解 P7156 [USACO20DEC] Cowmistry P
下一篇

芝加哥大学申请攻略:文书、成绩、环境……都在考验你!

你也可能喜欢

  • 暂无相关文章!

关注热点

返回顶部