題解 P7156 [USACO20DEC] Cowmistry P

題目大意：
給個(ge) 區間，問在所有區間的並中有多少個(ge) 三元組，滿足：
互不相同 . .輸出對取模。
數據範圍： .
題目難度：NOI/NOI+/CTSC

解析：
沒人寫(xie) 官方題解思路啊，那我寫(xie) 一手
首先對這樣就把轉化成了。定義(yi) 為(wei) 最小的的次冪使得，那麽(me) 顯然必須滿足（否則會(hui) 有且不為(wei) 0 的位出現）：
接下來分類討論：

此時在以上的位均為(wei) ，顯然滿足要求，統計相等的數量並對答案加上即可。
其他情況由於(yu) 以上的二進製位值都一樣，抽屜原理得出必有兩(liang) 項滿足。不妨考慮時的情況，由於(yu) 顯然有，隻用考慮對每個(ge) 求所有滿足的。
具體(ti) 地，有，集合為(wei) 所有且的，對於(yu) 該的答案就是。
下麵考慮如何實現，首先我們(men) 將每個(ge) 原區間按上述討論拆為(wei) 長度為(wei) 的整塊和不到的散塊。對於(yu) 長度為(wei) 的塊，答案為(wei)
接下來把散塊離線處理，
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);//第二類 } }第一類的答案很好統計，考慮如何處理第二類。可以將第二類劃分為(wei) 更小的兩(liang) 個(ge) 區間進行計算，這樣的分治最多進行層，可以通過。
時間複雜度： .
#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; }