CXJY-Day 6
异或(xor)
【题目描述】 有$n(n≤10000)$个盒子，每个盒子里装着一个非负整数$a_i$。给定非负整数$K,X$，现在你拥有一种魔法，每次使用魔法时，你任意挑选恰好K个盒子，将每一个盒子里的数变成它异或$X$，即如果原来盒子里的数是A，使用魔法后变成了$A xor X$，其中xor表示异或运算。
现在你可以任意次使用这种魔法，问在使用任意次魔法后，所有盒子里的数的总和最大是多少？
【输入格式】 第一行一个正整数T，表示数据组数。
对于每组数据，第一行一个正整数n。
第二行n个非负整数$a_i$，表示盒子里的初始数字。
第三行一个非负整数K
第四行一个非负整数X
【输出格式】 每组数据输出一行答案。 【输入样例】
1
7
10 15 20 13 2 1 44
4
14【输出样例】
129【数据范围与约定】 对于30%的数据，$n≤10$
对于60%的数据，$0≤A_i≤1,0≤X≤1$
对于100%的数据，$T≤30,n≤10000,0≤a_i,X≤10^9,K≤n$
题解
贪心，如果k<n，可以把两次操作看成操作两个数
当k为奇数时，可以操作任意多个数，k为偶数时，只能操作偶数个数
特判k=0，n的情况
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[10005],b[10005],k,x;
ll ans=0;
void solve(){
cin>>n;
ans=0;
for (int i=1;i<=n;++i){
scanf("%d",&a[i]);
ans+=a[i];
}
cin>>k>>x;
for (int i=1;i<=n;++i){
b[i]=(a[i]^x)-a[i];
}
if (k==n){
ll tt=0;
for (int i=1;i<=n;++i) tt+=b[i];
ans+=max(tt,0LL);
cout<<ans<<endl;
return;
}
sort(b+1,b+n+1);
if (k&1){
for (int i=1;i<=n;++i) ans+=max(0,b[i]);
}else{
for (int i=n-1;i>=1;i-=2){
if (b[i]+b[i+1]>0) ans+=b[i]+b[i+1];
}
}
cout<<ans<<endl;
}
int main(){
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
int t;
cin>>t;
while (t--) solve();
return 0;
}路径计数(paths)
【题目描述】 给定一张$n(n≤250000)$个点的无向连通图，共有$n-1$条边，即给定的是一棵树。
对于树上的任意两个点，定义$P(u,v)$为点u和点v之间的最短路上的所有点的集合（包括u和v）。
现在有$Q(Q≤300000)$个询问，每次询问给出两个点u,v，问有多少个点对$a,b(a≤b)$，满足集合$P(u,v)$和集合$P(a,b)$有且仅有一个公共点。换句话说，要问有多少个点对$a,b(a≤b)$，使得a, b之间的最短路和u, v之间的最短路恰好相交于一个点。
【输入格式】 第一行两个正整数n,Q。
接下来n-1行每一行两个正整数x,y，表示x,y之间有一条边。
接下来Q行每行两个正整数u,v，表示一个询问。
【输出格式】 对于每个询问，输出一行答案。 【输入样例】
6 2
1 2
1 3
1 4
2 5
2 6
4 5
1 3【输出样例】
6
9【数据范围与约定】 对于100%的数据，$n≤250000,Q≤300000,k≤50000$
题解
倍增，$f[i]$为子树内部经过i的路径数，$f[i]=\frac{\sum size[son]*(sum[i]-size[son])}{2}$
$h[i][j]$表示经过从i到i的$2^j$祖先的链，且不在i的子树内的路径数，$h[i][0]=f[fa(i)]-size[i]*(sum[fa(i)]-size[i])$
$h[i][j]=h[i][j-1]+h[fa[i][j-1]][j-1]$
然后倍增计算即可，特别需要注意lca处的处理
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int Next,y;
}Pth[500005];
int cnt,head[250005];
void add(int x,int y){
cnt++;
Pth[cnt].Next=head[x];
Pth[cnt].y=y;
head[x]=cnt;
}
int n,q,t,lc,son1,son2;
ll siz[250005],fa[250005][20],de[250005],sum[250005];
ll ta[250005],ans[250005][20],A;
void init(int x,int prv){
siz[x]=1;
for (int i=head[x];i;i=Pth[i].Next){
int y=Pth[i].y;
if (y==prv) continue;
init(y,x);
siz[x]+=siz[y];
ta[x]+=(ll)sum[x]*siz[y];
sum[x]+=siz[y];
}
}
void bfs(){
queue <int> q;
q.push(1); de[1]=1;
while (!q.empty()){
int x=q.front(); q.pop();
for (int i=head[x];i;i=Pth[i].Next){
int y=Pth[i].y;
if (de[y]) continue;
de[y]=de[x]+1;
fa[y][0]=x; ans[y][0]=ta[x]-siz[y]*(sum[x]-siz[y]);
for (int j=1;j<=t;++j){
fa[y][j]=fa[fa[y][j-1]][j-1];
ans[y][j]=ans[y][j-1]+ans[fa[y][j-1]][j-1];
}
q.push(y);
}
}
}
int lca(int x,int y){
if (de[x]<de[y]) swap(x,y);
for (int i=t;i>=0;--i){
if (de[fa[x][i]]>=de[y]){
x=fa[x][i];
}
}
if (x==y) return x;
for (int i=t;i>=0;--i){
if (fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int main(){
freopen("paths.in","r",stdin);
freopen("paths.out","w",stdout);
cin>>n>>q;
t=(int)(log(n)/log(2));
for (int i=1;i<n;++i){
int x,y;
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
init(1,-1);
bfs();
while (q--){
int x,y;
scanf("%d%d",&x,&y);
A=0;
lc=lca(x,y);
if (x!=lc) A+=ta[x];
if (y!=lc) A+=ta[y];
son1=son2=-1;
if (x!=lc){
for (int i=t;i>=0;--i)
if (de[fa[x][i]]>de[lc]){
A+=ans[x][i];
x=fa[x][i];
}
son1=x;
}
if (y!=lc){
for (int i=t;i>=0;--i)
if (de[fa[y][i]]>de[lc]){
A+=ans[y][i];
y=fa[y][i];
}
son2=y;
}
ll t=sum[lc];
if (son1!=-1) t-=siz[son1];
if (son2!=-1) t-=siz[son2];
A+=ta[lc];
if (son1!=-1) A-=siz[son1]*(sum[lc]-siz[son1]);
if (son2!=-1) A-=siz[son2]*(sum[lc]-siz[son2]);
if (son1!=-1 && son2!=-1) A+=siz[son1]*siz[son2];
A+=t*(n-siz[lc])+n;
printf("%lld\n",A);
}
return 0;
}难题(hard)
【题目描述】 有一个n行m列共计$n*m（1≤n,m≤10^5）$个格子的网格图，给定正整数$K(K≤10^9)$，你可以在每一个格子内填一个在$[1,K]$区间内的任意的正整数。对于一个填完数的网格图，定义数组A和B：$A_i (i=1,2,…,n)$为第i行的最大值，$B_i (i=1,2,…,m)$为第i列的最大值。
如果让你在格子内任意填数，你可以得到多少种不同的$(A,B)$？$(A,B)$与$(A’,B’)$不同当且仅当存在i使得$A_i≠A_i’$或者存在i使得$B_i≠B_i’$。（即A中存在至少一个数不同或B中存在至少一个数不同即为两个方案互不相同）
输出答案模$10^9+7$。
【输入格式】 第一行一个正整数T，表示数据组数。
每组数据包含一行三个正整数n,m,K。 【输出格式】 输出一行答案，模10^9+7。 【输入样例】
2
2 3 2
41 42 2【输出样例】
22
903408624【数据范围与约定】 对于100%的数据，$T≤1000,n,m≤10^5,K≤10^9$
对于100%的数据，所有T组数据中n的和不超过$10^5$，m的和不超过$10^5$
题解
发现只要满足a数组最大值与b数组最大值相等，即可生成对应的矩阵
30% $$ans=\sum_{i=1}^K (i^m-(i-1)^m)(i^n-(i-1)^n)$$即枚举ab数组的最大值，计算最大值为i时的两数组的方案数相乘即可
50% $$ans=\sum_{i=1}^K i^{n+m}-(i-1)^{n+m}-i^n(i-1)^m-i^m(i-1)^n$$具体不会
100% 拉格朗日插值。。。也不会 引理：$f^k(n)=\sum_{i=1}^{n}i^k$必定能用k+1次多项式函数表示
拉格朗日插值公式$$\ell_{j}(x)=\prod\limits_{ {i=0,\,i\neq j}}^{ {k}}{\frac{x-x_{i}}{x_{j}-x_{i}}}={\frac{(x-x_{0})}{(x_{j}-x_{0})}}\cdots{\frac{(x-x_{ {j-1}})}{(x_{j}-x_{ {j-1}})}}{\frac{(x-x_{ {j+1}})}{(x_{j}-x_{ {j+1}})}}\cdots{\frac{(x-x_{ {k}})}{(x_{j}-x_{ {k}})}}$$
在实际的OI竞赛中，选手常常要自己代值插值，所以我们一般选择$(0,f^k(0)),…,(k,f^k(k))$，带入L(x)有
$$f^k(n)=L(n)=\sum_{j=0}^{k+1}\frac{f^k(j)n(n−1)\dots(n−j+1)(n−j−1)\dots(n−k−1)(−1)^{k+1−j}}{j!(k+1−j)!}$$n为需要求的函数值
Link 因此本题的求和结果必然是一个$n+m+1$次多项式，带入$n+m+2$个值，用拉格朗日插值法即可求出$f(k)$的值，特别的，当$k<n+m+2$时，直接计算即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,N=300005;
ll fact[N],f[N],n,m,k;
ll fpow(ll x,ll y) {
ll res=1;
while (y) { if (y&1) res=res*x%mod; x=x*x%mod,y>>=1; }
return res;
}
ll add_mod(ll x) { return (x+mod)%mod; }
int main() {
freopen("hard.in","r",stdin); freopen("hard.out","w",stdout);
ll T; scanf("%lld",&T);
fact[0]=1; for (ll i=1; i<=200005; i++) fact[i]=fact[i-1]*i%mod;
while (T--) {
scanf("%lld%lld%lld",&n,&m,&k);
for (ll i=1; i<=n+m+2; i++) f[i]=(f[i-1]+add_mod(fpow(i,m)-fpow(i-1,m))*add_mod(fpow(i,n)-fpow(i-1,n))%mod)%mod;
if (k<=n+m+2) { printf("%lld\n",f[k]); continue; }
ll ans=1,t=0;
for (ll j=1; j<=n+m+2; j++) ans=ans*(k-j)%mod,t=(t+add_mod(f[j]*fpow(-1,n+m+2-j)%mod*fpow(fact[j]*fact[n+m+2-j]%mod*(k-j)%mod,mod-2)%mod))%mod;
printf("%lld\n",t*ans%mod*k%mod);
}
return 0;
}树
-
树形DP
CF1097G
考虑$k=1$的情况，枚举每条边，贡献为$(2^s-1)(2^{n-s-1}-1)$
考虑$1<k$的情况，每次枚举k条边，增加的贡献即为包含这些边的点集个数
$dp[i][j]$表示只在i的子树内，选出j条边对答案的贡献
树上倍增
严格次小生成树
无根树，给定一颗无根树$n<=100000$，有k次询问，每次求出根在x是y与z的lca，并求出y，z到lca的距离
分别求出3个lca
保卫王国
sunrise，一条路上从左到右分布着n个加油站，第i个加油站油价为pi，链接i到i+1的道路距离为di，你有一辆车，每开一公里耗1单位油，油箱容量为v。有m次询问，每次询问从a到b且初始有l单位油的最小花费
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-6/
