NC222470. [USACODec2020P]Cowmistry
描述
输入描述
The first line contains two integers N and K.
Each of the next N lines contains two space-separated integers li and ri. It is guaranteed that the boxes of cow-michals are provided in increasing order of their contents; namely, ri<li+1 for each 1≤i<N.
输出描述
The number of mixtures of three different cow-michals Bessie can create, modulo 109+7.
示例1
输入:
1 13 0 199
输出:
4280
说明:
We can split the chemicals into 13 groups that cannot cross-mix: (0…15), (16…31), … (192…199). Each of the first twelve groups contributes 352 unique mixtures and the last contributes 56 (since all (83) combinations of three different cow-michals from (192…199) are okay), for a total of 352⋅12+56=4280.示例2
输入:
6 147 1 35 48 103 125 127 154 190 195 235 240 250
输出:
267188
说明:
Test cases 3-4 satisfy max(K,rN)≤104.C++ 解法, 执行用时: 257ms, 内存消耗: 88880K, 提交时间: 2023-08-17 07:49:58
/** * 这题是一个非常恶心的分类讨论题。 首先可以将所有的二进制建在一个trie树上,然后进行dp。 设𝑑𝑝[𝑖] 表示三个二进制的LCA是属于i的子树。 然后一个显然的转移:𝑑𝑝[𝑖]=𝑑𝑝[𝑙[𝑖]]+𝑑𝑝[𝑟[𝑖]] ,也就是LCA分别属于两个儿子的子树,或者三个数的LCA正好是𝑖 。也就是有一个走到了一边,两个到了另一边。 可以发现难以用这个dp状态算分叉的情况。 所以我们引入𝑑𝑝2[𝑖][𝑗] 表示两个属于i的子树,一个属于j的子树, 需要哪个落单的必须和那两个xor起来<=k,𝑖≠𝑗。可以发现, 到了这一步前面的所有数𝑥𝑜𝑟 起来正好是k的前缀。 所以我们可以通过𝑖推出𝑗。也就是说,我们只需要记录𝑑𝑝2[𝑖] 就好了。 𝑑𝑝2[𝑖] 的转移:𝑑𝑝2[𝑙[𝑖]]+𝑑𝑝2[𝑟[𝑖]]+那两个在𝑖处再次分叉+已经可以保证≤𝑘。 然后再次分叉的又不好算了,我们再引入𝑑𝑝1[𝑖][𝑗]。 表示一个在i的子树,一个在j的子树,的方案数,可以用上面的观察,优化到一维𝑑𝑝1[𝑖]。转移也比较简单。 */ #include<bits/stdc++.h> #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a<b;++a) #define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define random(a) rng()%a #define ALL(a) a.begin(),a.end() #define POB pop_back #define ff fflush(stdout) #define fastio ios::sync_with_stdio(false) #define check_min(a,b) a=min(a,b) #define check_max(a,b) a=max(a,b) using namespace std; //inline int read(){ // int x=0; // char ch=getchar(); // while(ch<'0'||ch>'9'){ // ch=getchar(); // } // while(ch>='0'&&ch<='9'){ // x=(x<<1)+(x<<3)+(ch^48); // ch=getchar(); // } // return x; //} const int INF=0x3f3f3f3f; typedef pair<int,int> mp; /*} */ const int MOD=1e9+7; int n,k; vector<int> cover; vector<int> ls,rs; vector<int> depth; vector<int> match; int get(int num,int pos){ return (num>>(30-pos))&1; } int getval(int num,int pos){ return num&((1<<pos)-1); } void expand(int idx,bool flag=false){ if(ls[idx]) return; ls[idx]=cover.size(); rs[idx]=cover.size()+1; cover.PB(0); cover.PB(0); ls.PB(0),ls.PB(0); rs.PB(0),rs.PB(0); depth.PB(depth[idx]+1); depth.PB(depth[idx]+1); match.PB(0); match.PB(0); if(flag){ cover[ls[idx]]=cover[rs[idx]]=1<<(30-depth[ls[idx]]); } expand(match[idx],(cover[match[idx]]!=0)); if(get(k,depth[idx]+1)){ match[ls[idx]]=(rs[match[idx]]); match[rs[idx]]=(ls[match[idx]]); } else{ match[ls[idx]]=(ls[match[idx]]); match[rs[idx]]=(rs[match[idx]]); } } void insert(int root,int l,int r,int is=0){ if(l>r) return; cover[root]+=(r-l+1); if(r-l+1==(1<<(30-depth[root]))){ queue<int> q; q.push(root); while(!q.empty()){ int now=q.front(); q.pop(); if(now!=root){ cover[now]+=1<<(30-depth[now]); } if(ls[now]){ q.push(ls[now]); q.push(rs[now]); assert(rs[now]); } } // cout<<root<<' '<<match[root]<<" "<<l<<' '<<r<<' '<<depth[root]<<' '<<cover[root]<<endl; return; } expand(root); int mid=is; mid+=1<<(30-depth[root]-1); insert(ls[root],l,min(r,mid-1),is); insert(rs[root],max(l,mid),r,mid); } vector<int> dp1,dp2,dp3,g1,g2,g3; /* dp1[i]:一个选在i为根的子树,另一个选在match[i]为根的子树 dp2[i]:两个选在i为根的子树,另一个选在match[i]为根的子树 dp3[i]: i为根的子树的方案 */ const int SIX=166666668; void calc1(int rt){ if(!cover[rt]) return; if(ls[rt]==0){ if(cover[rt]&&cover[match[rt]]){ dp1[rt]=1<<(30-depth[rt]); dp1[rt]=1ll*dp1[rt]*(getval(k,30-depth[rt])+1)%MOD; } return; } calc1(ls[rt]); calc1(rs[rt]); dp1[rt]=dp1[ls[rt]]+dp1[rs[rt]]; dp1[rt]%=MOD; if(get(k,depth[rt]+1)){ (dp1[rt]+=1ll*cover[ls[rt]]*(cover[ls[match[rt]]])%MOD)%=MOD; (dp1[rt]+=1ll*cover[rs[rt]]*(cover[rs[match[rt]]])%MOD)%=MOD; } } void calc2(int rt){ if(!cover[rt]) return; if(ls[rt]==0){ if(cover[rt]&&cover[match[rt]]){ dp2[rt]=g2[30-depth[rt]]; } return; } calc2(ls[rt]); calc2(rs[rt]); dp2[rt]=dp2[ls[rt]]+dp2[rs[rt]]; dp2[rt]%=MOD; if(get(k,depth[rt]+1)){ (dp2[rt]+=(1ll*dp1[ls[rt]]*cover[rs[rt]]%MOD+1ll*dp1[rs[rt]]*cover[ls[rt]]%MOD)%MOD)%=MOD; (dp2[rt]+=1ll*cover[ls[rt]]*(cover[ls[rt]]-1)/2%MOD*(cover[ls[match[rt]]])%MOD)%=MOD; (dp2[rt]+=1ll*cover[rs[rt]]*(cover[rs[rt]]-1)/2%MOD*(cover[rs[match[rt]]])%MOD)%=MOD; } } void calc3(int rt){ if(!cover[rt]) return; if(ls[rt]==0){ if(cover[rt]) dp3[rt]=g3[30-depth[rt]]; return; } calc3(ls[rt]); calc3(rs[rt]); if(get(k,depth[rt]+1)){ (dp3[rt]+=dp2[ls[rt]])%=MOD; (dp3[rt]+=dp2[rs[rt]])%=MOD; dp3[rt]+=1ll*(cover[ls[rt]])*(cover[ls[rt]]-1)%MOD*(cover[ls[rt]]-2)%MOD*SIX%MOD; dp3[rt]%=MOD; dp3[rt]+=1ll*(cover[rs[rt]])*(cover[rs[rt]]-1)%MOD*(cover[rs[rt]]-2)%MOD*SIX%MOD; dp3[rt]%=MOD; } else{ dp3[rt]=dp3[ls[rt]]+dp3[rs[rt]]; dp3[rt]%=MOD; } } int main(){ scanf("%d%d",&n,&k); cover.PB(0); ls.PB(0); rs.PB(0); depth.PB(0); match.PB(0); rb(i,1,n){ int l,r; scanf("%d%d",&l,&r); insert(0,l,r); } int n=cover.size()-1; g1.resize(n+1); g2.resize(n+1); g3.resize(n+1); dp1.resize(n+1); calc1(0); rb(i,0,30){ g2[i]=1<<i; g2[i]=1ll*(getval(k,i)+1)*(getval(k,i))/2%MOD*g2[i]%MOD; } dp2.resize(n+1); calc2(0); dp3.resize(n+1); rb(i,2,30){ if((k>>(i-1))&1){ g3[i]+=2ll*g2[i-1]%MOD; g3[i]%=MOD; int tmp=1<<(i-1); tmp=2ll*tmp*(tmp-1)%MOD*(tmp-2)%MOD*SIX%MOD; (g3[i]+=tmp)%=MOD; } else{ g3[i]=g3[i-1]<<1; g3[i]%=MOD; } } calc3(0); printf("%d\n",dp3[0]); return 0; }