A. T1
考虑每一位对\(f\)的贡献，假设有\(x\)个\(a_i\)该位为\(1\)
code
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
ll x = 0; char c = getchar();
while(c < '0' || c > '9')c = getchar();
do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');
return x;
}
const int maxn = 100005;
ll n, l, r;
ll work(){
if(l == r)return 1;
int hi = 0; for(int i = 63; i >= 0; --i)if(((1ll << i) & l) != ((1ll << i) & r)){hi = i; break;}
int low = -1; for(int i = hi - 1; i >= 0; --i)if(r & (1ll << i)){low = i; break;}
ll nans = (1ll << hi) - (l & ((1ll << hi) - 1)), rl = (1ll << hi) - nans;
ll lr = (1ll << (low + 1)) - 1;
nans = nans << 1;
return nans + min(lr, rl - 1) + 1;
}
int main(){
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
int T = read();
for(register int ask = 1; ask <= T; ++ask){
n = read(), l = read(), r = read();
if(n > 1)printf("%lld\n",work());
else printf("%lld\n", r - l + 1);
}
return 0;
}
B. T2
考场刚推出对称差虎哥就发解释了..
这题先说对于任意四元组，在一棵树上有且仅有一种划分
划分在同一侧的两组在树上路径没有交，中间有一条链相连
于是我们可以枚举删去一条边或者一个点来容斥
由于一个四元组在边上统计的次数比在点上统计的次数多\(1\)，所以加上删边的贡献，减去删点的贡献
然后我们枚举在第一棵树上删了啥，对删除后在不同块的树点进行染色，在第二棵树上统计交集（枚举删去点/边，选所有不同颜色的组合，分别在不同子树内选取某种颜色的二元组），根据点/边决定是加上还是减去
这样$ S \Delta S^,= 2 \times C_{leaf}^4 - ans$
uglycode
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<assert.h>
using namespace std;
typedef long long ll;
inline int read(){
int x = 0; char c = getchar();
while(c < '0' || c > '9')c = getchar();
do{x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}while(c <= '9' && c >= '0');
return x;
}
const int maxn = 50005;
vector<int>g1[maxn], g2[maxn];
int leaf, n, col;
int cc[5], f[maxn][5];
ll ans, nans;
//edge - node = 1
int select2(int x){
// assert(x >= 0);
return x * (x - 1) / 2;
}
void solve(int x, int fa){
// if(x <= leaf)return;
int ls = 0, rs = 0;
for(int v : g2[x]){
if(v == fa)continue;
solve(v, x);
f[x][1] += f[v][1];
f[x][2] += f[v][2];
f[x][3] += f[v][3];
if(ls)rs = v; else ls = v;
}
if(!ls || !rs)return;
// assert((ls == 0 && rs == 0) || (ls != 0 && rs != 0));
if(fa){
int f1 = cc[1] - f[x][1], f2 = cc[2] - f[x][2], f3 = cc[3] - f[x][3];
nans = nans - select2(f1) * (0ll + select2(f[ls][2]) + select2(f[ls][3]) + select2(f[rs][2]) + select2(f[rs][3]));
nans = nans - select2(f2) * (0ll + select2(f[ls][1]) + select2(f[ls][3]) + select2(f[rs][1]) + select2(f[rs][3]));
nans = nans - select2(f3) * (0ll + select2(f[ls][1]) + select2(f[ls][2]) + select2(f[rs][1]) + select2(f[rs][2]));
// printf("tree 2 node : %d del node now nans = %lld\n", x, nans);
}
nans = nans - select2(f[ls][1]) * (0ll + select2(f[rs][2]) + select2(f[rs][3]));
nans = nans - select2(f[ls][2]) * (0ll + select2(f[rs][1]) + select2(f[rs][3]));
nans = nans - select2(f[ls][3]) * (0ll + select2(f[rs][1]) + select2(f[rs][2]));
// printf("tree 2 node : %d del node now nans = %lld\n", x, nans);
nans = nans + select2(f[ls][1]) * (0ll + select2(cc[2] - f[ls][2]) + select2(cc[3] - f[ls][3]));
nans = nans + select2(f[ls][2]) * (0ll + select2(cc[1] - f[ls][1]) + select2(cc[3] - f[ls][3]));
nans = nans + select2(f[ls][3]) * (0ll + select2(cc[1] - f[ls][1]) + select2(cc[2] - f[ls][2]));
// printf("tree 2 node : %d del edge - > %d now nans = %lld\n", x, ls, nans);
nans = nans + select2(f[rs][1]) * (0ll + select2(cc[2] - f[rs][2]) + select2(cc[3] - f[rs][3]));
nans = nans + select2(f[rs][2]) * (0ll + select2(cc[1] - f[rs][1]) + select2(cc[3] - f[rs][3]));
nans = nans + select2(f[rs][3]) * (0ll + select2(cc[1] - f[rs][1]) + select2(cc[2] - f[rs][2]));
// printf("%d %d %d %d %d %d\n",f[rs][1], f[rs][2], f[rs][3], cc[1], cc[2], cc[3]);
// printf("tree 2 node : %d del edge - > %d now nans = %lld\n", x, rs, nans);
}
void upd(int x, int fa){
for(int i = 1; i <= 4; ++i)f[x][i] = 0;
// printf("upd : %d %d %d\n", x, fa, col);
if(x <= leaf){ ++f[x][col]; ++cc[col]; return; }
for(int v : g1[x]) if(v != fa)upd(v, x);
}
void del(int x, int fa){
col = 0; cc[1] = cc[2] = cc[3] = 0;
for(int v : g1[x]){
for(int i = 1; i <= 4; ++i)f[x][i] = 0;
++col, upd(v, x);
}
nans = 0; solve(1, 0); ans = ans - nans;
// printf("del node : %d now nans = %lld\n\n",x , nans);
for(int v : g1[x]){
if(v == fa)continue;
cc[1] = cc[2] = cc[3] = 0;
col = 1; upd(v, x); col = 2; upd(x, v);
nans = 0; solve(1, 0); ans = ans + nans;
// printf("del edge : %d < - > %d now nans = %lld\n\n",x, v, nans);
}
for(int v : g1[x])if(v != fa)del(v, x);
}
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
leaf = read(); n = leaf + leaf - 2;
for(int i = 1; i < n; ++i){
int u = read(), v = read();
g1[u].push_back(v), g1[v].push_back(u);
}
for(int i = 1; i < n; ++i){
int u = read(), v = read();
g2[u].push_back(v), g2[v].push_back(u);
}
del(n, 0);
ans = 1ll * leaf * (leaf - 1) * (leaf - 2) * (leaf - 3) / 12 - ans - ans;
printf("%lld\n",ans);
return 0;
}