计算机科学学习笔记
文件输入输出要注意，文件名不要打错，一定要复制。
文件要独立。
打表要用文件输出，防止手抖。
随手 ctrl+s 。
输入不要想当然，n m 不要弄反。
变量不要冲突。
DevC++ 可能会放一些莫名其妙的代码过。有的可能交上去 CE 的本地可以编译通过。头文件一定要记得开。
multi_set 删点的时候不能指定名字并删除，要找到以后再删除。
逻辑或是用在bool上的。
三目运算符和逗号的优先级。位运算的优先级。实在拿不准就加括号。
结构体内重载运算符如果类型不对可能会 CE ，记得要写 const 。
ull 的左移有坑！！！
快速幂的底数要先取模，因为 long long 乘 long long 可能会爆掉。
多测要清空，但不要 memset ，同 dsu on tree 。
退役了。
Day1 大众分应该是 210 。
记住，写东西的时候要写 1ull<<N ，而非 1<<N 。 我 T1 在这里被卡了一个多小时，直接导致 T3 没有时间写暴力。 T2 反正大家都会做就不说了，大概就是树形 DP ，优化一下状态转移。有一个 trick 就是括号可以考虑前缀和什么的。 T3 不会做。不过 35pts 的暴力其实还是挺好想的。实在是时间不够。 估分 200 pts。
Day2 大众分应该是 263 。
T1 整个人都傻了。一道傻逼容斥居然没想出来。其实挺显然的，提示也给得很多，但是大概是题面太长，给了一些干扰吧。写了 m=3 的暴力走人。 T2 人没了。大概花了二十分钟左右的时间猜了一个结论，感觉挺正确的，大概就是如果你能分割最多份并且每一份的大小都尽可能小，那么答案是最优的。写了份代码调了一下。反正就记一个 g 函数表示以当前点结尾的最小值。然后记一下前缀和移项用单调栈优化一下转移就好了。然后写了个暴力拍了一下。还写了个高精。结果最后暴力拍出问题了。人都傻了，只好把暴力交上去走人。结果出来一对答案，发现我正解写得是对的，暴力写挂了。人没了。 T3 没有仔细想，写了 55 分的暴力。其实二叉树的结论挺好想的，但是没认真打，其实打了还是收益更高的。 想来想去还是 T2 犯的错太可惜了，一下子少掉了一大堆分。 估分 119 pts。
总估分 319 pts。
其实本来就知道这场已经是退役场了，只是没想到会退役得那么惨。
高一开始搞 OI ，当时意气风发。然后从 NOIP 到省选，再到 CTSC-APIO ，接二连三地，总是没能发挥出全力、总是出现这样那样的问题、总是把能拿的分给丢了。
其实考试的时候的题并不是题题都那么难。但是一方面自己经验不足，在考场上总是会出现这样那样的错误，有的时候是对分数的估计没有那么准确，有的时候是一些小点不知道导致调题调了很久，有的时候是没看出来一些显然的结论。大概是写题的时候总是没有理清思路吧。
所以就退役了吧，也就断了这份念想。
说到底还是菜。但是只是「菜」这个字是无法概括的。「菜」是有很多种形式的、是由很多个部分构成的。如果没有仔细地分析其中的每一个成分，那就没办法解决这个问题。
其实最近的出题趋势有点向国外靠拢的意思，也就是，大码农题逐渐变少，而有趣的结论题、有一定思维难度的题则增多。其代表就是 DP 题的逐渐增加。 从这个角度上说，刷一刷 Atcoder 或者 Codeforces 的意义是很大的。 然而我并没有发现这个趋势，也没有认真地培养自己的思维能力。
当然另一方面就是代码能力的问题。譬如，如果那一次和 XRJ 一起手写 bitset ，那我在 Day1T1 ，就不会在那个错上花那么多时间。
还有就是考试策略。实际上，考试的时候，应当要看好每一个部分分、预估一下难度。这样可能会发挥得更好一些。诸如 D1T1 为了 5pts 花了一个多小时、 D2T2 为了 12pts 花了快一个小时，都是相似的原因。
说到底，就是这样一个风气：我 A 了这道题，所以我牛逼。 但是其实考场上这个心态是毫无意义的。 然而 AC 实在是太爽了。你看到那一片大大的绿色，正反馈简直是无穷的。 所以即便明白这个道理也很难改正。
再有一个问题就是做题时的劲。唯独在考试的时候才能有一种无往不利的锐气，才能想出很多平时呆坐半天都无法解决的结论。说不定是猜结论的时候胆子不够大吧。
说也挺可笑的，我现今怀念以前的时候比展望未来的时候竟要多得多。 即便到了今日，对现今的状况仍然没有什么实感。实感想必是之后的事情了。
又有什么可说的呢？ 那就这样了吧。
「过去的事情就过去了吧。」这样的话实在是太好说出口了。然而正是这种话太好说出口，所以不免惹得疑心这事情是否曾经挂在心上。 或许在多年之后，我仍然会梦回今日，遗憾着当时的 Day2 怎么考得那么差。但是 CSP2019 只不过是一个迟来的句号，就好比古典音乐结束之后那悠扬的尾声淡出于空气之中的那个位置。我的 OI 生涯其实早在那之前就结束了。
今から後悔しても無駄です。
这个博客我也许还会挂在这里，留待以后使用；也许会就此关停。 但那又有什么关系呢，这毕竟只是个写给自己看的博客啊。
在最后的时刻看到他们在讨论 D2T2 ，我又想冲上去把我 D2T2 犯的错大说特说，毕竟这是我此刻要紧的感受。
然后在此时我突然意识到：那又有什么用呢？他们尚且有下一年，而我已经不在此间了。
于是疏离感淹没了我。
我的手离开了键盘。
挺套路的。
先计算出所有数的积的逆元，再计算除了这个数以外的数的积，然后乘一起，这样就完成了线性求逆元。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=5000005;
inline int rd(){
int rt=0;char ch=getchar();
while(!isdigit(ch)){ch=getchar();}
while(isdigit(ch)){rt=rt*10+ch-'0';ch=getchar();}
return rt;
}
int n,MOD,k;
int a[N],pr[N],sf[N];
inline int pw(int A,int X){
int RT=1;
while(X){
if(X&1){
RT=1ll*RT*A%MOD;
}
A=1ll*A*A%MOD;X>>=1;
}
return RT;
}
void init(){
scanf("%d%d%d",&n,&MOD,&k);
int pl=1;
pr[0]=sf[n+1]=1;
for(int i=1;i<=n;++i){
a[i]=rd();
}
for(int i=1;i<=n;++i){
pr[i]=1ll*pr[i-1]*a[i]%MOD;
}
pl=pw(pr[n],MOD-2);
for(int i=n;i>=1;--i){
sf[i]=1ll*sf[i+1]*a[i]%MOD;
}
int nk=1;
int ans=0;
for(int i=1;i<=n;++i){
nk=1ll*nk*k%MOD;
ans+=1ll*(1ll*pr[i-1]*sf[i+1]%MOD)*(1ll*pl*nk%MOD)%MOD;ans%=MOD;
}
printf("%d\n",ans);
}
int main(){
init();
return 0;
}
这实际上是一个 Tarjan 求割点的裸题。
具体来说是这样的。首先，对于每一个连通块，答案显然是独立的。然后，一个连通块至少要有两个出口——这也是容易理解的。
接下来，我们把所有点双都缩成一个点，这时候整张图就一定是一棵无根树。
我们观察这棵树。如果树上只有一个节点，那么两个出口就都必须设在这个点双中；如果树上有多个节点，那么有且仅有叶子节点要各自设一个出口：这是因为，对于非叶子节点，它都有多条路走向叶子节点。
现在问题是如何求出这棵树。我们不妨用 Tarjan 来求。
Tarjan 是一种用于求点双联通分量的常用算法，以其发明者 Tarjan 所命名。特别需要注意的是，这里用到的是 Tarjan 求割点的部分，而不是像圆方树那样求点双的部分。
对于一个点，我们记两个数组，dfn 和 lw，分别表示它的 dfs 序和它在 dfs 树的子树内的所有节点的返祖边中 dfs 最小的节点。
如果某一个节点，它是根节点，并且它在 dfs 树上有超过一个子节点，那么它必然是割点——这是由 dfs 树的性质决定的。
如果一个节点，它的子节点的 lw 总是大等于它的 dfn ，那么就说明它的这棵子树内的所有节点只能抵达它或者它子树内的点，因而它必然是割点。
结合这两条性质即可找出点双。
然后统计一下即可。存在一定的细节。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=505;
struct ee{
int v;
int nxt;
}e[N<<2];
struct Data{
int u;int v;
}lst[N<<2];
int g[N],h[N],et=0;
inline void Eadd(int U,int V,int *H){
e[++et]=(ee){V,H[U]};
H[U]=et;
}
inline void add(int U,int V,int *H){
Eadd(U,V,H);
Eadd(V,U,H);
}
int n;
int dfn[N],lw[N],dfsid=0,cnt=0,ag[N],sn[N];
inline void dfs0(int X,int FA){
dfn[X]=lw[X]=++dfsid;sn[X]=0;
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v==FA){
continue;
}
if(!dfn[e[i].v]){
++sn[X];
dfs0(e[i].v,X);
lw[X]=min(lw[X],lw[e[i].v]);
if((FA&&lw[e[i].v]>=dfn[X])){
ag[X]=1;
}
}else{
lw[X]=min(lw[X],dfn[e[i].v]);
}
}
if(!FA&&sn[X]>1){
ag[X]=1;
}
}
ll vis[N],sm[N],tot[N],cal,sz,nv,deg[N];
inline void dfs1(int X){
vis[X]=nv;++sz;
for(int i=h[X];i;i=e[i].nxt){
if(vis[e[i].v]==nv){
continue;
}
if(ag[e[i].v]){
vis[e[i].v]=nv;++cal;
continue;
}
dfs1(e[i].v);
}
}
ll ans,cans,nt;
void init(){
cnt=et=dfsid=nt=0;
for(int i=1;i<=n;++i){
h[i]=dfn[i]=lw[i]=vis[i]=sm[i]=tot[i]=deg[i]=ag[i]=0;
}
int u,v;
for(int i=1;i<=n;++i){
scanf("%d%d",&u,&v);
add(u,v,h);
++deg[u];++deg[v];
lst[i]=(Data){u,v};
nt=max(nt,1ll*u);nt=max(nt,1ll*v);
}
for(int i=1;i<=nt;++i){
if(!dfn[i]){
dfs0(i,0);
}
}
// for(int i=1;i<=nt;++i){
// printf("%d ",ag[i]);
// }
// puts("");
ans=0,cans=1;
for(int i=1;i<=nt;++i){
if(ag[i]){
if(deg[i]<=1){
++ans;
}
}else if(!vis[i]){
nv=i;cal=0;sz=0;
dfs1(i);
if(cal==1){
++ans;cans*=sz;
}else if(cal==0){
ans+=(sz==1?1:2),cans*=(sz==1?1:sz*(sz-1)/2);
}
}
}
}
int main(){
scanf("%d",&n);
int T=0;
while(n){
++T;
init();
printf("Case %d: %lld %lld\n",T,ans,cans);
scanf("%d",&n);
}
init();
return 0;
}
额…看起来是一道找规律题，实际上还是挺有门道的。
题目的题意就是，求 n 个点的点、边均有标号的生成树个数。
n 个点的无根有标号生成树个数，根据某个叫做 Cayley 的古老定理， 值是：
当然，由于边有标号，所以这里的值还要乘上一个。
问题是 Cayley 定理要如何证明。
一种比较简易的方法是一种被称为 Prufer 序列的构造。通过这种构造，我们发现，有且仅有 种不同的方法来构造一棵有标号无根树。
这个序列是如何构造的呢？
我们考虑递归地构造这个序列。对于当前的树，我们选其中的编号最小的叶子节点，将它的相邻点——显然是唯一的——加入序列，然后删掉这个叶子节点。
这样，我们就得到了一个序列。这个序列中每一个点的出现次数是它的入度 -1 。
由此我们可以构造出这个序列。
通过 Prufer 序列，我们无损地将一棵有标号无根树的信息压缩成了一个序列。
那么要怎么把 Prufer 序列还原为一棵有标号无根树呢？我们有一种系统的方法。
首先选择一个数，这个数既不在已有的树中，也不在当前的序列中，并且它最小。那么，我们就可以确定，这个数便是我们当前要处理的叶子节点。
然后，我们把这个节点与当前枚举到的序列中的点连边。这等于是逆向还原 Prufer 序列的生成过程。
是不是对于任何一个值域在 n 范围内的长度为 n-2 的序列都可以还原成一棵树呢？
假设我们当前正在处理第 i 个节点，序列中剩下 k 种数，那么已经被作为叶子节点，已经连接或即将被连接的节点数则是 n-k 个。每处理一个节点，至多会消耗掉一个叶子节点的配额。因此已经连接的节点至多为 i-1 个。又因为 n-2-i+1 必须大于等于 k ，所以叶子节点必然不会不够。
那么完成最后一步以后叶子节点会不会有剩呢？每个节点会被连接的次数正好是它在序列中出现的次数 +1 ，这也就意味着，总度数恰好是 2n-2 ，由于每一条边都无向，所以构成的正好是一张 n-1 条边的图。
最后的疑问就是构成的图是不是连通的。考虑到 n-1 条边的连通图与 n-1 条边的无环图是等价的，我们不妨尝试证明它无环。
我们称，一个点被作为「要处理的叶子节点」来连接的过程为「向上连边」，那么每个点的向上连边操作会且仅会发生一次。在这种情况下，环会出现，只有可能是「向上连边」的时候连向的是自己所在的连通块内的点。
然而，向上连边的目标，一定还在 Prufer 序列中，而可以向上连边的点，一定不在 Prufer 序列中。我们于是证明了这张图无环。
既然这张 n-1 条边的图无环，那么它一定连通。
由此，我们发现，每一棵树都能唯一对应地生成一个 Prufer 序列，并且每一个 Prufer 序列都能生成一棵树。
这样我们就证明了 Prufer 序列和有标号无根树的一一对应性。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=9999991;
inline ll pw(ll A,ll X){
ll RT=1;
while(X){
if(X&1){
RT*=A;
RT%=MOD;
}
A*=A;A%=MOD;X>>=1;
}
return RT;
}
int n;
void init(){
scanf("%d",&n);
ll fac=1;
for(int i=1;i<n;++i){
fac=fac*i%MOD;
}
printf("%lld\n",pw(n,n-2)*fac%MOD);
}
int main(){
init();
return 0;
}
我们尝试类比序列上的情况来看这一题。
对于序列上的情况，我们维护一个集合 \(S\) ，其中 \(S_i\) 表示，长度为 \(i\) 的最长不下降子序列的最后一项的最小值。 那么，对于新的点，我们考虑两种情况：它能加长序列，那么就加长；否则，就尽可能地更新最小值。
对于树上的情况，我们首先尝试考虑一种 \(O(n^2logn)\) 的做法。我们对于每一个节点维护一个集合 \(S_i\)， 其中 \(S_{i,j}\) 表示仅用到这个节点及其子树内的所有点，能够构造的大小为 \(j\) 的集合的最小项的最大值。
如果我们把所有子节点的 \(S\) 都已经整合在一起了，那么更新根节点是比较容易的：类比于序列即可。 问题在于子节点要如何合并。
仔细观察，发现，子节点的合并是一个类似于归并的操作。 这样我们就有了一个 \(O(n^2logn)\) 的「高」效做法。
怎么优化这个做法呢？ 我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 \(O(nlog^2n)\) ，足以通过此题。 具体来说，我们对于每个节点开一个map，然后暴力合并。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=200005;
struct ee{
int v;
int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
int w[N],sz[N],sn[N],dep[N],fa[N];
int id[N];
multiset<int> lst[N];
int n;
inline void dfs0(int X){
sn[X]=0,sz[X]=1;
for(int i=h[X];i;i=e[i].nxt){
dfs0(e[i].v);
sz[X]+=sz[e[i].v];
if(sz[sn[X]]<sz[e[i].v]){
sn[X]=e[i].v;
}
}
}
inline void dfs1(int X){
if(sn[X]){
dfs1(sn[X]);
id[X]=id[sn[X]];
}
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v==sn[X]){
continue;
}
dfs1(e[i].v);
lst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());
}
lst[id[X]].insert(w[X]);
multiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);
if(it!=lst[id[X]].begin()){
--it;lst[id[X]].erase(it);
}
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&w[i]);
id[i]=i;
}
int x;
for(int i=2;i<=n;++i){
scanf("%d",&x);
fa[i]=x;add(x,i);
}
dfs0(1);
dfs1(1);
printf("%d\n",lst[id[1]].size());
}
int main(){
init();
return 0;
}Polya定理是一个关于置换群中组合计数的定理。
首先我们来了解Burnside引理。这个引理的证明较为复杂，在这里仅介绍其内容。
Burnside引理的内容是这样的：在置换意义下本质不同的染色方案数，等于单个置换不会改变的染色方案数的平均值。
那么，单个置换不会改变的染色方案数要怎么求呢？我们不妨把置换关系建成一张图，那么这张图必然由若干个环构成。也就是说，对于同一种置换，可能存在若干个环，而每个初始状态就是环上的一个节点。Polya定理描述的就是，某一种置换不会改变的方案数，等于颜色数的「这个置换对应的循环节个数」
阐述了上述两个定理，现在我们来看这一题。
我们观察到，这个环上存在 n 种置换。对于置换 i 而言，它的循环大小是：
$$
\frac{n}{\gcd(n,i)}
$$
这也就意味着，它的循环个数是：
$$
\gcd(n,i)
$$
那么我们要求的答案就是：
$$
\frac{\sum_{i=1}^nn^{(n,i)}}{n}
$$
然而这样计算答案的复杂度是 O(n) 的，我们无法接受。
我们不妨考虑枚举这个公因子。那么，容易证明的是，每一个公因子d对应的置换个数是\(\varphi(\frac{n}{d})\)
这是因为， d 是 \(\frac{n}{d}\) 个数的因数，而这些数中，如果它和\(\frac{n}{d}\)存在公因子的话，那么它和n的最大公因数必然大于d。
所以，我们求的就是：
$$
\frac{\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}}}{n}=\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}-1}
$$
我们只要枚举n的因数即可。
然而求这里的 \(\varphi\) 倒可能存在一些问题。事实上，由于我们要取的因数的值域是 \(10^9\) ，我们无法使用欧拉筛来预处理，而需要现场做。
这样的复杂度是不是对的呢？它的最坏情况是 \(O(Tn^{\frac{3}{4}})\) 的，但由于我并不会分析的一些性质，它不会达到这个值。因此可以通过此题。
另：括号忘记加，爆O泪两行。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
const int N=1000005;
inline ll pw(ll A,ll X){
ll RT=1;
while(X){
if(X&1){
RT*=A;RT%=MOD;
}
A*=A;A%=MOD,X>>=1;
}
return RT;
}
int n;
inline int phi(int X){
int RT=1;
for(int i=2;i*i<=X;++i){
if(X%i==0){
X/=i;RT*=i-1;
while(X%i==0){
X/=i;RT*=i;
}
}
if(X==1){
break;
}
}
if(X>1){
RT*=X-1;
}
return RT;
}
void init(){
scanf("%d",&n);
ll ans=0;
for(int i=1;i*i<=n;++i){
if(n%i==0){
ans+=(1ll*phi(n/i)*pw(n,i-1))%MOD;
if(i*i!=n){
ans+=(1ll*phi(i)*pw(n,n/i-1))%MOD;
}
ans%=MOD;
// printf("%d %lld\n",i,ans);
}
}
printf("%lld\n",ans);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
}
return 0;
}
贪心构造即可。
具体来说，如果把a依次标成-n…-1，那么只会有三种数：0（贡献是下标-1），n（贡献是0）以及x（贡献是下标比x小且<-x）的数。
贪心地构造，可以保证x只出现一次。暴力枚举检验即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=300005;
int n;ll m;
int a[N],b[N],p[N],q[N];
int bckt[N];
void init(){
scanf("%d%lld",&n,&m);
for(int i=0;i<=n;++i){
bckt[i]=0;
}
for(int i=1;i<=n;++i){
scanf("%d",&p[i]);
a[p[i]]=-n+i-1;
}
for(int i=1;i<=n;++i){
scanf("%d",&q[i]);
if(m==0){
b[q[i]]=n;
}else if(m>=q[i]-1){
m-=q[i]-1;
b[q[i]]=-1;
}else{
for(int j=1;j<q[i];++j){
++bckt[a[j]+n];
}
for(int j=1;j<=n;++j){
bckt[j]+=bckt[j-1];
}
for(int j=1;j<q[i];++j){
if(bckt[a[j]+n]==m){
m=0;b[q[i]]=-a[j]-1;
break;
}
}
}
}
puts("Yes");
for(int i=1;i<=n;++i){
printf("%d ",a[i]);
}
puts("");
for(int i=1;i<=n;++i){
printf("%d ",b[i]);
}
puts("");
}
int main(){
init();
return 0;
}