成绩
比赛经过
糟糕记不清了？
\(\text{A}\) 题，结论很显然，不出意外应该是很快就搞出来了，但是没有考虑所给的子图可能不连通！挂成 \(\text{50}\) 了？
\(\text{B}\) 题，一眼 \(\text{DP}\) 事实证明我是对的。但是我对一个子问题 \(\text{DP}\)。考虑的是 \(0\) 时刻的方案选取数，本来想用 \(bitset\) 水过去，奈何不会搞。（没想到直接对答案 \(\text{DP}\) 时间复杂度更优秀？）
\(\text{C}\) 题，我去，二次函数上凸壳？这不会啊，暴力（对了 \(32\) 分然后一分不给？）
\(\text{D}\) 题，从数据范围的特殊限制，就已经猜到和阶有关了（特殊性质：保证是 \(p\) 的原根），大概是个循环类似的题吧（蒙对了？？？）。然后不会做，特殊性质打表拿了 \(10\) 分。
赛后补题+分析
\(\text{A}\) Tree
简要/形式化题意
给定一棵弱连通树的子图，记一棵弱连通树的值为：给弱连通树赋边权 \(0/1\)，使得 \(1\) 到任意某个可达结点的边权和大于 \(0\)。求这颗弱连通树的值对 \(p\) 取余的最大值。
题解
- 树确定时，答案为 \(2^{n-1-k}\)。 \(k\) 为从 \(1\) 出发可达结点中的相邻结点个数。
- 给定子图后，\(n\) 个结点 \(cnt\) 个连通块。不属于 \(1\) 结点所在连通块的每个连通块，要么选择一个结点作为 \(1\) 的可达结点中的相邻结点，要么都不是。因此，这样的 \(cnt-1\) 个连通块对 \(k\) 的贡献为 \(0/1\)。因此 \(k\) 的范围为 \([sonbase,sonbase+cnt-1]\)。\(sonbase\) 为 \(1\) 所在连通块的可达结点中的相邻结点的个数。暴力枚举即可。时间复杂度 \(O(n)\)。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,p,u,v,sonbase,Ans,cnt;
int flag[N];
int ksm(int a,int b,int P) {
int ans=1%P;
for(;b;b>>=1) {
if(b&1) ans=ans*a%P;
a=a*a%P;
}
return ans;
}
struct node {
int fa[N];
void cleanr(int n) {
for(int i=1;i<=n;i++) fa[i]=i;
}
int find(int x) {
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y) {
int fx=find(x),fy=find(y);
if(fx!=fy) fa[fx]=fy;
}
}BCJ;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>p;
BCJ.cleanr(n);
for(int i=1;i<=m;i++) {
cin>>u>>v;
BCJ.merge(u,v);
if(u==1) sonbase++;
}
for(int i=1;i<=n;i++) flag[BCJ.find(i)]=1;
for(int i=1;i<=n;i++) cnt+=flag[i];
for(int i=sonbase;i<=sonbase+cnt-1;i++)
Ans=max(Ans,ksm(2,n-1-i,p));
cout<<Ans;
return 0;
}