A. Parsa's Humongous Tree
题目描述
给一棵树，试确定 (a_iin[l_i,r_i]) 使得 (sum |a_u-a_v|) 最大，其中 ((u,v)) 在原树上有边连接。
解法
这道题我先猜了一个结论，(a_i=l_ior a_i=r_i)
证明好像并不难，使用调整法，如果 (a_i ot=l_iand a_i ot=r_i)，那么调整到 (l_i) 或 (r_i) 不会使答案变得更差。
然后搞个树 (dp) 即可，时间复杂度 (O(n))
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 100005;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,tot,f[M],l[M],r[M],dp[M][2];
struct edge
{
int v,next;
}e[2*M];
int Abs(int x) {return x>0?x:-x;}
void dfs(int u,int fa)
{
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u);
dp[u][0]+=max(dp[v][0]+Abs(l[u]-l[v]),dp[v][1]+Abs(l[u]-r[v]));
dp[u][1]+=max(dp[v][1]+Abs(r[u]-r[v]),dp[v][0]+Abs(r[u]-l[v]));
}
}
void work()
{
n=read();tot=0;
for(int i=1;i<=n;i++)
{
l[i]=read();r[i]=read();
dp[i][0]=dp[i][1]=f[i]=0;
}
for(int i=1;i<n;i++)
{
int u=read(),v=read();
e[++tot]=edge{v,f[u]},f[u]=tot;
e[++tot]=edge{u,f[v]},f[v]=tot;
}
dfs(1,0);
printf("%lld
",max(dp[1][0],dp[1][1]));
}
signed main()
{
T=read();
while(T--) work();
}
B. Kavi on Pairing Duty
题目描述
(2n) 个点排列在 (x) 轴上，第 (i) 个点的坐标是 (i)，把这 (2n) 个点划分成 (n) 对，问满足下列条件的划分数量：
对于任意点对 (A,B)，连成的线段要不然长度一样，要不然存在包含关系。
(1leq nleq 10^6)
解法
设 (dp[n]) 为有 (2n) 个点的划分方案数，考虑一小步的转移，我们选择长度为 (i) 的点对连成线段，因为它们不存在包含关系，所以只有在它们交叉的部分会形成子问题，我们来讨论两种情况：
- 如果 (igeq n)，那么在当前问题只有一种划分方案，但是递归下去会形成所有 (x<n) 的子问题，所以这时候用 (sum_{i=0}^{n-1} dp[i]) 加上去即可。
- 如果 (i<n)，那么没有递归子问题，必须统计出所有线段没有公共部分的方案，这等价于把 (2n) 划分成若干个连续段，每个连续段长度为偶数，设 (f[i]) 为 (i) 偶数真因数个数，那么把 (f[2n]) 加上去即可，这个很容易预处理。
时间复杂度 (O(nlog n))
#include <cstdio>
const int MOD = 998244353;
const int M = 2000005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,f[M],dp[M];
void init(int n)
{
for(int i=2;i<=n;i+=2)
for(int j=2*i;j<=n;j+=i)
f[j]++;
}
signed main()
{
init(2e6);
n=read();
for(int i=1,s=1;i<=n;i++)
{
dp[i]=(s+f[2*i])%MOD;
s=(s+dp[i])%MOD;
}
printf("%d
",dp[n]);
}
C. Trees of Tranquillity
题目描述
给定两棵以 (1) 为根 (n) 个点的树，建一个新图，如果满足下列条件的 ((u,v)) 就连边：
- 在第一棵树中 (u,v) 存在祖先(-)子代关系。
- 在第二棵树中 (u,v) 不存在祖先(-)子代关系。
求这个新建图最大团，即一个集合满足任意两点都有直接边相连。
(2leq nleq 3cdot 10^5)
解法1
首先观察到一个比较重要的性质：选出来的点在第一棵树上构成一条链（虽然可能会中断）。
那么就先考虑一个简化的问题，如果只有第一棵树是一条链我们怎么做？
(dp) 是不好 (dp) 的，换一种方法吧。可以把这条链上的点在第二棵树上标记出来，然后每次加入一个点就考虑贪心地优化答案，如果这个点的祖先有被选的，用它替换祖先是更优的；如果这个点的子代有被选的，这个点就不会存在答案中；否则直接把这个点选上去。
判断祖先和子代有无被选点可以用 ( t dfs) 序(+)线段树完成，考虑扩展到普通的树，其实就是在访问到某个点的时候在第二棵树上考虑这个点，回溯的时候撤回操作，这样访问到每个点的时候维护的都是从根到它一条链的情况了。
时间复杂度 (O(nlog n))
#include <cstdio>
#include <vector>
using namespace std;
const int M = 300005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,Ind,now,ans,l[M],r[M],s[4*M],tag[4*M],tr[4*M];
vector<int> g1[M],g2[M];
void pre(int u,int fa)
{
l[u]=++Ind;
for(int i=0;i<g2[u].size();i++)
{
int v=g2[u][i];
if(v==fa) continue;
pre(v,u);
}
r[u]=Ind;
}
void down(int i)
{
if(tag[i]==-1) return ;
tr[i<<1]=tr[i<<1|1]=tag[i<<1]=tag[i<<1|1]=tag[i];
tag[i]=-1;
}
void add1(int i,int l,int r,int id,int x)//add a tag to a certain point
{
if(l==r) {s[i]+=x;return ;}
int mid=(l+r)>>1;
if(id<=mid) add1(i<<1,l,mid,id,x);
else add1(i<<1|1,mid+1,r,id,x);
s[i]=s[i<<1]+s[i<<1|1];
}
int ask1(int i,int l,int r,int L,int R)//ask the tag in subtree
{
if(L<=l && r<=R) return s[i];
if(L>r || l>R) return 0;
int mid=(l+r)>>1;
return ask1(i<<1,l,mid,L,R)+ask1(i<<1|1,mid+1,r,L,R);
}
void add2(int i,int l,int r,int L,int R,int x)//update the subtree
{
if(L<=l && r<=R) {tr[i]=tag[i]=x;return ;}
if(L>r || l>R) return ;
int mid=(l+r)>>1;down(i);
add2(i<<1,l,mid,L,R,x);
add2(i<<1|1,mid+1,r,L,R,x);
}
int ask2(int i,int l,int r,int id)
{
if(l==r) return tr[i];
int mid=(l+r)>>1;down(i);
if(mid>=id) return ask2(i<<1,l,mid,id);
return ask2(i<<1|1,mid+1,r,id);
}
void dfs(int u,int fa)
{
int t1=ask1(1,1,n,l[u],r[u]),t2=ask2(1,1,n,l[u]);
if(!t1)
{
if(!t2) now++;
add1(1,1,n,l[u],1);
if(t2) add2(1,1,n,l[t2],r[t2],0);
add2(1,1,n,l[u],r[u],u);
}
ans=max(ans,now);
for(int i=0;i<g1[u].size();i++)
{
int v=g1[u][i];
if(v==fa) continue;
dfs(v,u);
}
if(!t1)//call back the operation
{
if(!t2) now--;
add1(1,1,n,l[u],-1);
add2(1,1,n,l[u],r[u],0);
if(t2) add2(1,1,n,l[t2],r[t2],t2);
}
}
signed main()
{
T=read();
while(T--)
{
n=read();Ind=now=ans=0;
for(int i=1;i<=n;i++)
g1[i].clear(),g2[i].clear();
for(int i=1;i<=4*n;i++)
s[i]=tr[i]=0,tag[i]=-1;
for(int i=2;i<=n;i++)
{
int j=read();;
g1[i].push_back(j);
g1[j].push_back(i);
}
for(int i=2;i<=n;i++)
{
int j=read();
g2[i].push_back(j);
g2[j].push_back(i);
}
pre(1,0);
dfs(1,0);
printf("%d
",ans);
}
}
解法2
( t xjx) 给了一种更简洁的方法，也就是选出的点在第二棵树上满足 ([l_i,r_i]) 不交，其中 (l_i,r_i) 分别代表子树欧拉序的左右端点。
然后还是在第一棵树上 ( t dfs)，由于欧拉序区间只存在包含或者不交的关系，他用维护了所有的线段，如果有包含它的线段那么就可以贪心替换，如果没有区间和它有交那么可以直接插入，用 ( t set,map) 都可以维护。
#include<cstdio>//JZM YYDS!!!
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#define ll long long
#define MAXN 300005
#define uns unsigned
#define MOD 998244353ll
#define INF 0x3f3f3f3f
using namespace std;
inline ll read(){
ll x=0;bool f=1;char s=getchar();
while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar();
return f?x:-x;
}
int n,IN;
int bg[MAXN],ed[MAXN],ans;
vector<int>G[MAXN],G_[MAXN];
struct node{
int x,y;node(){}
node(int X,int Y){x=X,y=Y;}
bool operator<(const node&b)const{
if(b.x!=x)return x<b.x;
else return y>b.y;
}
};
map<node,bool>mp;
map<node,bool>::iterator it;
inline void dfs_(int x){
bg[x]=++IN;
for(uns i=0;i<G_[x].size();i++)dfs_(G_[x][i]);
ed[x]=IN;
}
inline void dfs(int x){
node cg=node(0,0);
bool ok=1;
mp[node(bg[x],bg[x])],it=mp.find(node(bg[x],bg[x]));
if(it!=mp.begin()){
it--;
if(it->first.y>=bg[x])cg=it->first;
it++;
}
it++;
if(it!=mp.end()&&it->first.x<=ed[x])ok=0;
mp.erase(node(bg[x],bg[x]));
if(ok){
if(cg.x)mp.erase(cg);
mp[node(bg[x],ed[x])];
}
ans=max(ans,(int)mp.size());
for(uns i=0;i<G[x].size();i++)dfs(G[x][i]);
if(ok){
if(cg.x)mp[cg];
mp.erase(node(bg[x],ed[x]));
}
}
signed main()
{
for(int T=read();T--;){
n=read(),IN=0,ans=1;
for(int i=1;i<=n;i++)
G[i].clear(),G_[i].clear(),bg[i]=ed[i]=0;
for(int i=2;i<=n;i++)G[read()].push_back(i);
for(int i=2;i<=n;i++)G_[read()].push_back(i);
mp.clear();
dfs_(1),dfs(1);
printf("%d
",ans);
}
return 0;
}
D. It's a bird! No, it's a plane! No, it's AaParsa!
题目描述
给定 (n) 个点 (m) 条边的有向图，在第 (s) 秒第 (i) 条边的终点会变为 ((b_i+s)\%n)，问所有点对的最短路。
(2leq nleq 600,mleq n^2)
解法
这道题最重要的就是不能把时间放进最短路的状态里面，有一个重要的提示：Note that AaParsa can stay in a city for as long as he wants，也就是说我们只需要用到每个点的最短路去扩展即可。
对于那么现在的问题是计算边权了，设到 (u) 的最短路是 (d)，则让边 (i) 指向 (v) 的实际边权是：
(e[i].c+cal((e[i].u+d)\%n,v))
其中 (cal(x,y)) 是 (x) 转到 (y) 的最小时间，那么每次扩展时扫两边就可以计算实际边权，跑 (n) 次 ( t dijkstra) 的复杂度是 (O(n^3)) 的，这道题不加堆优化好像要快一些，但是我还是卡过去了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int M = 605;
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,tot,f[M],a[M],dis[M],vis[M];
struct edge
{
int v,c,next;
}e[M*M];
struct node
{
int u,c;
bool operator < (const node &r) const
{
return c>r.c;
}
};
void work(int s)
{
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
priority_queue<node> q;
dis[s]=0;q.push(node{s,0});
while(!q.empty())
{
int u=q.top().u,d=q.top().c;q.pop();
if(vis[u]) continue;vis[u]=1;
for(int i=0;i<n;i++) a[i]=inf;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
a[(v+d)%n]=e[i].c;
}
for(int i=0,mi=inf;i<n;i++)
{
mi=min(mi,a[i]-i);
if(dis[i]>d+mi+i)
{
dis[i]=d+mi+i;
q.push(node{i,dis[i]});
}
}
for(int i=n-1,mi=inf;i>=1;i--)
{
mi=min(mi,a[i]+n-i);
int j=i-1;
if(dis[j]>d+mi+j)
{
dis[j]=d+mi+j;
q.push(node{j,dis[j]});
}
}
}
}
signed main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),c=read();
e[++tot]=edge{v,c,f[u]},f[u]=tot;
}
for(int i=0;i<n;i++,puts(""))
{
work(i);
for(int j=0;j<n;j++)
printf("%lld ",dis[j]);
}
}
E. Mashtali and Hagh Trees
题目描述
称一棵有向树为阿七树当且仅当满足如下条件：
- 这棵树的最长有向路径是长度 (n)
- 以点任意点 (u) 为端点的有向边不超过 (3) 条
- (u,v) 是朋友当且仅当 (u) 能到 (v) 或者 (v) 能到 (u)，树上任意两点要么是朋友要么有一个共同的朋友。
给定 (n)，问不同构的阿七树有多少个，答案模 (998244353)
(1leq nleq 10^6)
解法
这道题最好不要直接从有向树的角度入手，我们可以把树分层，有向边的起点划分在上层，终点划分在下层。
在这个分层图上考虑 (u,v) 是朋友的条件，发现总有一个根，满足它和上层能构成一棵树，它和下层也能构成一棵有向树。考虑最长有向路径长度是 (n) 的条件，就等价于这个分层图的高度是 (n)
那么我们确定根上面的树和根下面的树再用乘法原理即可，设 (dp(i,j)) 表示高度为 (i) 的树根节点度数是 (j) 的方案数，我们用最上面的根来统计某一棵树的答案，所以要强制上面树的深度为 (2)，上面树为空要特殊讨论，所以可以写出答案：
现在的问题变成了算 (dp(i,j))，可以定义 (f(i,j)) 表示高度至少为 (i) 的树根节点度数是 (j) 的方案数，这个要好转移一些，假设子树一共有 (x) 中选法，那么相当于从中选出 (j) 个来组成这个树，由于要考虑同构问题我们对于相同的子树种类是不存在顺序的，这相当于 (x) 个非负整数的和为 (j)，方案数是 ({x+j-1choose j})，至于 (x) 就是 (sum_{j=0}^2 f(i-1,j))，最后再差分回来即可。
时间复杂度 (O(n))
#include <cstdio>
const int M = 1000005;
const int MOD = 998244353;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,ans,dp[M][4],inv[4]={0,1,(MOD+1)/2,(MOD+1)/3};
int C(int n,int m)
{
int r=1;
if(n<m) return 0;
for(int i=0;i<m;i++) r=r*(n-i)%MOD;
for(int i=1;i<=m;i++) r=r*inv[i]%MOD;
return r;
}
signed main()
{
n=read();dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=3;j++)
{
int x=0;
for(int k=0;k<=2;k++)
x=(x+dp[i-1][k])%MOD;
dp[i][j]=C(x+j-1,j);
}
}
for(int i=n;i>=1;i--)
for(int j=0;j<=3;j++)
dp[i][j]=(dp[i][j]-dp[i-1][j]+MOD)%MOD;
for(int i=1;i<=n;i++)
for(int j=2;j<=3;j++)
for(int k=0;k<=3-j;k++)
ans=(ans+dp[i][j]*dp[n-i][k])%MOD;
for(int i=0;i<=3;i++)
ans=(ans+dp[n][i])%MOD;
printf("%lld
",ans);
}
F. AmShZ Farm
题目描述
(a,b) 都数组由 ([1,n]) 中的数字组成，(a) 数组长度为 (n)，并且满足给任意元素加上任意非负数后能变成某个排列，(b) 数组长度为 (k)，满足 (a_{b_1}=a_{b_2}=...=a_{b_k})（注意我们没有要求 (a,b) 数组的元素两两不同）
问有多少个本质不同的数组对 ((a,b))，答案取模 (998244353)
(1leq nleq10^9,1leq kleq 10^5)
解法
发现 (a,b) 两个数组的计数还算比较独立吧，我们先考虑 (a) 数组怎么计数。
设 (c_i) 为数字 (i) 的出现次数，则限制可以翻译为 (sum_{j=i}^{n} c_jleq n-i+1)，但是这样根本算不出来，因为这个限制牵扯到的东西太多了，我们想要更加独立的限制。
不妨把题目换个说法：我们有 (n+1) 个位置排成一排，有 (n) 个人要坐进来，第 (i) 个人一开始会到位置 (a_i)（(1leq a_ileq n)），如果位置已满就往编号大的位置走，如果最后剩下的位置是 (n+1) 的话就是一个合法的 (a) 序列。
这是一个经典的序列转等概率环模型（第二次见了），所以我们可以改写题目为：有 (n+1) 个位置排成一个环，有 (n) 个人要坐进来，第 (i) 个人一开始会到位置 (a_i)（(1leq a_ileq n+1)），如果位置已满就往右边走，如果最后剩下的位置是 (n+1) 的话就是一个合法的 (a) 序列。
因为是一个环并且初始到每个点的概率相同，所以每个点被空出来的概率也是相同的，不难发现方案数就是 ((n+1)^{n-1})
我们再深入下去剖析这个模型，对于每种合法的 (a) 序列都可以映射到 (n) 种不同的不合法序列，因为如果我们让 (a_i) 变成 ((a_i+x-1)\%(n+1)+1)，那么空出的位置 (t) 会变成 ((x+t-1)\%(n+1)+1)，由此引出一个重要的性质：对于这 (n+1) 个方案来说，数字的分布情况是不会改变的，所以我们可以统计出所有排列的答案再除以 (n+1)
(a) 数组差不多搞定了，我们来解决 (b) 数组的计数。
枚举数字 (x) 的出现次数 (i)，由于 (x) 有 (n+1) 种选择就自动除 (n+1)，所以可以写出答案式：
首先要观察式子再化简（官方题解不给推导过程差评），因为底数很大但是指数很小，所以使用斯特林反演：
这个式子最好固定的指数，所以我们把它带进 (i^k) 中：
这时候心理要有根弦（我要交作业），通常是用组合意义和二项式反演把式子化简的，因为要让 (i) 出现得尽量少，所以我们把 ({ichoose j}) 中的 (i) 给换走，那么这可以用一个组合恒等式：
把这个式子带进去，再调整一下顺序：
要用二项式反演是需要从 (0) 开始枚举的，所以我们把 (i) 调整成 (i-j)：
这是个明显的二项式反演了，所以可以得到最后的结果。
上面的式子显然可以 (O(nlog n)) 算，现在的问题就是快速算第二类斯特林数了，(S(n,m)) 的组合意义是 (n) 个不同的小球放在 (m) 个相同盒子的方案数，要求盒子非空，所以我们容斥空盒子数量：
因为盒子是相同的所以要除以盒子的排列 (frac{1}{m!})，可以通过变形让它可以卷积：
随便卷一下就可以做到 (O(nlog n))，所以总时间复杂度 (O(nlog n))
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 300005;
const int MOD = 998244353;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
namespace poly
{
int len,A[M],B[M],rev[M];
int qkpow(int a,int b)
{
int r=1;
while(b>0)
{
if(b&1) r=r*a%MOD;
a=a*a%MOD;
b>>=1;
}
return r;
}
void NTT(int *a,int len,int op)
{
for(int i=0;i<len;i++)
{
rev[i]=(rev[i>>1]>>1)|((len/2)*(i&1));
if(i<rev[i]) swap(a[i],a[rev[i]]);
}
for(int s=2;s<=len;s<<=1)
{
int t=s/2,w=(op==1)?qkpow(3,(MOD-1)/s):qkpow(3,MOD-1-(MOD-1)/s);
for(int i=0;i<len;i+=s)
for(int j=0,x=1;j<t;j++,x=x*w%MOD)
{
int fe=a[i+j],fo=a[i+j+t];
a[i+j]=(fe+x*fo)%MOD;
a[i+j+t]=((fe-x*fo)%MOD+MOD)%MOD;
}
}
if(op==1) return ;
int inv=qkpow(len,MOD-2);
for(int i=0;i<len;i++) a[i]=a[i]*inv%MOD;
}
void work(int n,int m,int *a,int *b,int *c)
{
len=1;while(len<n+m) len<<=1;
for(int i=0;i<len;i++) A[i]=B[i]=0;
for(int i=0;i<n;i++) A[i]=a[i];
for(int i=0;i<m;i++) B[i]=b[i];
NTT(A,len,1);NTT(B,len,1);
for(int i=0;i<len;i++) A[i]=A[i]*B[i]%MOD;
NTT(A,len,-1);
for(int i=0;i<n+m;i++) c[i]=A[i];
}
}
int n,k,ans,fac[M],inv[M],a[M],b[M],c[M];
void init(int n)
{
inv[0]=inv[1]=fac[0]=1;
for(int i=2;i<=n;i++) inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=2;i<=n;i++) inv[i]=inv[i]*inv[i-1]%MOD;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
}
signed main()
{
init(1e5);
n=read();k=read();c[0]=1;
for(int i=0;i<=k;i++)
{
a[i]=poly::qkpow(i,k)*inv[i]%MOD;
b[i]=(i%2)?(MOD-inv[i]):inv[i];
if(i>0) c[i]=c[i-1]*(n-i+1)%MOD*poly::qkpow(i,MOD-2)%MOD;
}
poly::work(k+1,k+1,a,b,a);
for(int i=0;i<=k;i++)
ans=(ans+a[i]*c[i]%MOD*poly::qkpow(n+1,n-i)%MOD*fac[i])%MOD;
printf("%lld
",ans);
}