题解 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; }