D1T1 冰火战士
Description
有两个元素集合 (S,T)，每个元素都有权值 (c,w)，(q) 次插入或删除一个元素，询问：
并求出达到最大值的 (t)，若有多个 (t) ，取其中最大的。
(qle 2 imes 10^6,c_ile 2 imes 10^9)。
Solution
首先最终的 (t) 一定会在某一个 (c_i) 处取到，因此可以先将 (c_i) 离散化。
由于最终求的是两坨东西的 (min) 的 (max)，（不妨设分别为 (a_t,b_t)），又注意到 (a_t) 是不降的函数，(b_t) 是不增的函数，因此答案一定在二者交界处附近取到，考虑先找到交界点，也就是 (a_t-b_t) 这一不降函数的零点。
求不降函数的零点，容易想到直接用线段树维护 (a_t-b_t)，然后在线段树上二分，这样做是 (mathcal O(nlog n)) 的，但常数较大，可能会被卡。
事实上，我们也可以用树状数组维护，具体而言，用两棵树状数组分别维护 (a_t) 与 (b_t)。找交界点时，假设现在我们正在 (pos) 位置（初始为 (0)），目前的 (a_{pos}-b_{pos}le 0)，然后考虑向后跳 (2) 的次幂，按 (d) 从大到小依次考虑 (now=pos+2^d) 是否依然满足 (a_{now}-b_{now}le 0) ，如果是，直接跳到 (now) 的位置，否则就不跳，将步幅减小。再判断新点是否符合时，新增的部分就是树状数组上点 (now) 维护的信息，因此可以 (mathcal O(1)) 进行判断。
至此我们 (mathcal O(nlog n)) 的找到了最大的使得 (a_tle b_t) 的 (t)，(t+1) 就是最小的 (a_t>b_t) 的 (t)，显然答案一定在它们中产生。注意当 (t+1) 为最终答案时，它不一定是所有这样的 (t) 中最大的，我们可以通过再一次二分来找到最终答案。
最终复杂度为小常数 (mathcal O(nlog n))。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int q,d[N],tot,ct[2];
struct node{
int t,x,y;
}a[N];
struct BIT{
int c[N];
inline int lowbit(int x){return x&(-x);}
inline void update(int x,int y){
for(;x<=tot;x+=lowbit(x)) c[x]+=y;
}
inline int query(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans+=c[x];
return ans;
}
}T[2];
int dt;
int main(){
scanf("%d",&q);
for(int i=1,op,k;i<=q;++i){
scanf("%d",&op);
if(op==1) scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].y);
else{
scanf("%d",&k);
a[i]=a[k];a[i].y=-a[i].y;
}
d[i]=a[i].x;
}
sort(d+1,d+q+1);
tot=unique(d+1,d+q+1)-d-1;
for(int i=1;i<=q;++i){
a[i].x=lower_bound(d+1,d+tot+1,a[i].x)-d;
int tp=a[i].t;
if(a[i].y>0) ct[tp]++;
else ct[tp]--;
if(!tp) T[0].update(a[i].x,a[i].y);
else T[1].update(a[i].x+1,-a[i].y),dt+=a[i].y;
if(!ct[0]||!ct[1]){puts("Peace");continue;}
int now=0,ret=-dt;
for(int i=20;i>=0;--i){
if(now+(1<<i)>tot) continue;
int x=now+(1<<i);
if(T[0].c[x]-T[1].c[x]+ret<=0) now=x,ret+=T[0].c[x]-T[1].c[x];
}
ret=min(T[0].query(now),T[1].query(now)+dt);
int tmp=min(T[0].query(now+1),T[1].query(now+1)+dt);
if(now<tot&&tmp>=ret){
int lim=T[1].query(now+1);
ret=0;now=0;
for(int i=20;i>=0;--i){
if(now+(1<<i)>tot) continue;
int x=now+(1<<i);
if(ret+T[1].c[x]>=lim) ret+=T[1].c[x],now=x;
}
ret=tmp;
}
if(!ret){puts("Peace");continue;}
printf("%d %d
",d[now],ret<<1);
}
return 0;
}
D1T2 组合数问题
Description
请求出：
其中 (f(k)) 是关于给定的一个 (m) 次多项式 (f(k)=sum_{i=0}^{m}a_ik^i)。
(mle 1000,n,x,ple 10^9)。
Soltion
首先将多项式展开：
注意到 (x^kdbinom nk) 类似二项式定理的形式，而前面这个 (k^i) 怎么看怎么不对劲，于是套路的将它转化为下降幂：
这是三项式系数，可以转化为
终于舒服了，二项式定理得到：
直接递推处理第二类斯特林数，即可做到 (mathcal O(m^2))
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010;
struct FastMod{
typedef unsigned long long ULL;
typedef __uint128_t LLL;
ULL b,m;
void init(ULL b){this->b=b,m=ULL((LLL(1)<<64)/b);}
ULL operator()(ULL a)const{
ULL q=(ULL)((LLL(m)*a)>>64);
ULL r=a-q*b;
return r>=b?r-b:r;
}
}mod;
inline ll operator %(ll x,const FastMod &mod){return mod(x);}
int n,x,md,m,a[N],str[N][N],base[N],low[N];
inline int ksm(int x,int y){
int ret=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
return ret;
}
inline void init(){
for(int i=str[0][0]=1;i<=m;++i){
for(int j=1;j<=m;++j)
str[i][j]=(str[i-1][j-1]+1ll*j*str[i-1][j])%mod;
}
low[0]=1;
for(int i=1;i<=m;++i) low[i]=1ll*low[i-1]*(n-i+1)%mod;
}
int main(){
scanf("%d%d%d%d",&n,&x,&md,&m);
mod.init(md);
init();
int ans=0;
for(int i=0;i<=m;++i){
scanf("%d",&a[i]);
int ret=0,pw1=1;
for(int j=0;j<=i;++j,pw1=1ll*pw1*x%mod)
ret=(ret+1ll*str[i][j]*low[j]%mod*pw1%mod*ksm(x+1,n-j))%mod;
ans=(ans+1ll*ret*a[i])%mod;
}
printf("%d
",ans);
return 0;
}
D1T3 魔法商店
这是一道神仙论文题，我在之前的博客保序回归问题中已进行了详细的讲解。
D2T1 信号传递
Description
有 (m) 个信号站，你可以任意安排它们在数轴上之间的顺序。
给定一个长度为 (n) 的数组 (S) 表示信号传递序列，表示要进行 (n-1) 次 (S_i o S_{i+1}) 的传输。如果两个分别位于 (a,b) 号位置上的信号塔要进行 (a o b) 传输，传输的代价为：
- 若 (ale b)，花费 (b-a)的代价传输。
- 若 (a >b)，花费 (k(b+a)) 的代价传输。
请求出最优情况下代价的最小值。
(mle 23,nle 10^5,kle 100)。
Solution
看到 (m) 这么小，考虑状压 (DP)，依次考虑从左到右第 (i) 位是那一个信号站，然后加入序列中。如何计算一个信号站的贡献？首先传输代价显然可以分到两点上独立计算，因此对于信号站 (x)，对于传输 (x ightarrow y) ，若 (y) 已经在序列中则付出 (kpos) 的代价，否则付出 (-pos) 的代价；对于传输 (y ightarrow x)，若 (y) 已经在序列中则付出 (pos) 的代价，否则付出 (kpos) 的代价，其中 (pos) 为 (x) 的值。
那么 (mathcal O(m^2)) 预处理出 (y) 信号站的存在与否对 (x) 代价的影响，即可 (mathcal O(m)) 的计算点 (x) 加入序列付出的代价。因此复杂度为 (mathcal O(2^mm^2))。
考虑优化，直接预处理 (f[i][s]) 表示当前序列中的信号站为 (s) 时，加入 (i) 的贡献，这可以直接从 (f[i][sotimes lowbit(s)]) 转移过来，只需要增加一个新数的贡献，因此预处理的复杂度为 (mathcal O(2^mm))，那么 (DP) 转移的复杂度也被优化到了 (mathcal O(2^mm))，可以通过此题。但是空间复杂度达到了 (23 imes 2^{23}) ，超过了空间限制。注意到我们需要考虑的 (f[i][s]) 中 (s) 是一定不会包含 (i) 的，因此 (s) 只有 (2^{m-1}) 个，就能将空间复杂度优化到 (23 imes 2^{22}) 了。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<23),M=1e5+10;
int f[N],s[M],n,m,k,pd[M],to[23][23],ru[23][23],g[23][1<<22],lg[N];
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i) scanf("%d",&s[i]),s[i]--;
for(int i=1;i<n;++i){
if(s[i]!=s[i+1]) to[s[i]][s[i+1]]++,ru[s[i+1]][s[i]]++;
}
for(int i=0;i<(1<<m);++i) f[i]=0x3f3f3f3f;
for(int i=0;i<m;++i) lg[1<<i]=i;
for(int i=0;i<m;++i){
for(int j=0;j<m;++j)
g[i][0]+=k*ru[i][j]-to[i][j];
for(int j=1;j<(1<<m-1);++j){
int p=j&(-j),x=lg[p];if(x>=i) x++;
g[i][j]=g[i][j^p]-(k*ru[i][x]-to[i][x])+(k*to[i][x]+ru[i][x]);
}
}
f[0]=0;
for(int i=0;i<(1<<m);++i){
int len=0;
for(int j=0;j<m;++j){
pd[j]=i&(1<<j);
if(pd[j]) len++;
}
for(int j=0;j<m;++j)
if(!pd[j]){
int num=i|(1<<j),tmp=(i&((1<<j)-1))|((i>>j+1)<<j);
f[num]=min(f[num],f[i]+g[j][tmp]*(len+1));
}
}
printf("%d
",f[(1<<m)-1]);
return 0;
}
D2T2 树
Description
给定一棵 (n) 个结点的有根树 (T)，每个结点有一个正整数权值 (w_i)。
请你求出
其中 (son_u) 为 (u) 子树中的点的集合。
(n,v_ile 525010)。
Solution
容易想到使用 (trie) 树维护一个点子树中的所有 (w)，那么我们就只需要完成以下操作：
- 单点插入
- 全局加1
- 合并两棵trie树
- 求全局异或和
(1,3,4) 是好做的，考虑 (2) 怎么做，如果还是向普通 (trie) 树一样从高到低维护，一层一层平移非常恶心；考虑改为从低位向高位维护，模拟一般的进位过程，将当前点的左儿子与右儿子交换，然后向左儿子递归下去即可。
那么接下来就是模板 (trie) 合并，其实现思路与线段树合并完全一致，复杂度也为 (mathcal O(nlog n))。为了支持 (4) 操作，我们对 (trie) 树上的每个点维护 (t_i) 表示 (i) 子树中的点的仅考虑从低到高第 (dep_isim 20) 位时的异或和，有：
这是因为，对于 (dep_i) 这一位，影响全局异或和是否为 (1) 的就是这一位 (1) 的个数，即 (siz_{rc})。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int H=21,N=6e5+10,M=N*H*2;
int n,v[N],fa[N];
ll ans;
vector<int> to[N];
int rt[N];
namespace Trie{
int ch[M][2],siz[M],del[M],tot,top,ret[M];
inline void Del(int x){ch[x][0]=ch[x][1]=siz[x]=ret[x]=0;del[++top]=x;}
inline int newnode(){return top?del[top--]:++tot;}
inline int merge(int p1,int p2,int dep){
if(!p1||!p2) return p1+p2;
if(dep==20){
siz[p1]=siz[p1]+siz[p2];
ret[p1]=0;
Del(p2);return p1;
}
ch[p1][0]=merge(ch[p1][0],ch[p2][0],dep+1);
ch[p1][1]=merge(ch[p1][1],ch[p2][1],dep+1);
Del(p2);
siz[p1]=siz[ch[p1][0]]+siz[ch[p1][1]];
ret[p1]=(ret[ch[p1][0]]^ret[ch[p1][1]])|((siz[ch[p1][1]]&1)<<dep);
return p1;
}
inline void work(int p,int dep){
if(!p) return ;
swap(ch[p][0],ch[p][1]);
work(ch[p][0],dep+1);
ret[p]=(ret[ch[p][0]]^ret[ch[p][1]])|((siz[ch[p][1]]&1)<<dep);
}
inline void insert(int &p,int x){
if(!p) p=newnode();
ret[p]^=x;
int now=p;siz[now]++;
for(int i=0;i<=20;++i){
int c=(x>>i)&1;
if(!ch[now][c]) ch[now][c]=newnode();
now=ch[now][c];siz[now]++;
ret[now]^=(x>>(i+1))<<(i+1);
}
ans+=ret[p];
}
}
using namespace Trie;
inline void dfs(int u){
for(int v:to[u]) dfs(v),rt[u]=merge(rt[u],rt[v],0);
work(rt[u],0);
insert(rt[u],v[u]);
// printf("%d %d
",u,ret[rt[u]]);
}
int main(){
// freopen("tree2.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&v[i]);
for(int i=2;i<=n;++i) scanf("%d",&fa[i]),to[fa[i]].push_back(i);
dfs(1);
cerr<<Trie::tot<<endl;
printf("%lld
",ans);
return 0;
}
D2T3 作业题
Description
给定一个 (n) 个顶点 (m) 条边的无向图 (G)，保证图中无重边和无自环。每一条边有一个正整数边权 (w_i)，对于一棵 (G) 的生成树 (T)，定义 (T) 的价值为(T) 所包含的边的边权的最大公约数乘以边权之和。请你求出 (G) 所有生成树的价值和。
(nle 30,mle dfrac{n(n-1)}{2},w_ile 152501)。
Solution
大力莫比乌斯反演生成树价值的柿子：
于是直接大力枚举 (i)，然后仅保留 (w) 是 (i) 倍数的边，剩下的问题就是求一张图的所有生成树边权和了，使用矩阵树定理可以做到 (mathcal O(n^3))。同时注意到边数如果 (<n-1) ，就可以直接忽略一定没有生成树，因此总复杂度为 (mathcal O(n^2dfrac{sum sigma_0(w_i)}{n-1}))，可以通过此题。
对于矩阵树定理如何做权值和的问题，考虑朴素的做法，固定某一条边，它的边权不变，然后将其他边的权值都定为(1)，然后再按权值积的方法来计算，这样就能求出这条边的贡献了。
这样做的背后是我们希望作权值积时，这个积是有一个边权和若干个(1)组成的，这令你想到什么了吗？多项式：如果我们将每一个边权都变化为一个形如 (wx+1) 的多项式，其中 (w) 是这条边的边权，那么最后求出的权值积的一次项系数就是答案。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=31,M=2e5+10,mod=998244353;
int n,m,u[N*N],v[N*N],w[N*N],mx;
int phi[M],p[M],f[M],pcnt;
inline void init(int n){
phi[1]=1;
for(int i=2;i<=n;++i){
if(!f[i]) p[++pcnt]=i,phi[i]=i-1;
for(int j=1;j<=pcnt&&i*p[j]<=n;++j){
int num=i*p[j];f[num]=1;
if(i%p[j]) phi[num]=1ll*phi[i]*phi[p[j]]%mod;
else{phi[num]=1ll*phi[i]*p[j]%mod;break;}
}
}
}
struct poly{
int x,y;
poly(int _x=0,int _y=0){x=_x;y=_y;}
}d[N][N];
inline int add(int x,int y){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
inline int ksm(int x,int y){
int ret=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
return ret;
}
inline poly operator +(const poly &a,const poly &b){return poly(add(a.x,b.x),add(a.y,b.y));}
inline void operator +=(poly &a,const poly &b){a=a+b;}
inline poly operator -(const poly &a,const poly &b){return poly(dec(a.x,b.x),dec(a.y,b.y));}
inline void operator -=(poly &a,const poly &b){a=a-b;}
inline poly operator *(const poly &a,const poly &b){return poly((1ll*a.x*b.y+1ll*a.y*b.x)%mod,1ll*a.y*b.y%mod);}
inline poly ginv(const poly &a){
poly t=poly(0,ksm(a.y,mod-2));
return poly(0,2)*t-t*t*a;
}
inline int Gauss(int n){
poly ans=poly(0,1);
for(int i=1;i<=n;++i){
if(!d[i][i].y){
for(int j=i+1;j<=n;++j)
if(d[j][i].y){swap(d[i],d[j]);ans=mod-ans;break;}
}
ans=ans*d[i][i];
poly iv=ginv(d[i][i]);
for(int j=i;j<=n;++j) d[i][j]=d[i][j]*iv;
for(int j=i+1;j<=n;++j){
poly tmp=d[j][i];
for(int k=n;k>=i;--k) d[j][k]=d[j][k]-(tmp*d[i][k]);
}
}
return ans.x;
}
inline int matrix_tree(int x){
int ct=0;
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) d[i][j]=poly(0,0);
for(int i=1;i<=m;++i){
if(w[i]%x==0){
ct++;
poly tmp=poly(w[i],1);
d[u[i]][u[i]]+=tmp;d[v[i]][v[i]]+=tmp;
d[u[i]][v[i]]-=tmp;d[v[i]][u[i]]-=tmp;
}
}
if(ct<n-1) return 0;
return Gauss(n-1);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) scanf("%d%d%d",&u[i],&v[i],&w[i]),mx=max(mx,w[i]);
init(mx);
int ans=0;
for(int w=1;w<=mx;++w)
ans=(ans+1ll*phi[w]*matrix_tree(w))%mod;
printf("%d
",ans);
return 0;
}