前言

130pts
20+100+10
终于没有挂分！
开心！
然而今天的题确实过于阴间…三道题几乎都没法写暴力，爆零场了属于是。
我这个分数都能到rnk4勒。
（rnk39->rnk4，乐）

考场

一拿题我就觉得不太妙。
T1数树题，第一眼看到输入一个数输出一个数就想到应该是生成函数+多项式，但是不给NTT模数？
难道这玩意能dp？
…本场满分200分。
T2看起来还挺正常的，把二分写脸上了。
T3题如其名，动态沙漠玩期望，《毒瘤》，我突然发现自己仙人掌是一道题都没做过，感觉可能要LCT罢，但是那个期望我也没什么想法…本场满分100分。

20min，我差不多明白了本场考试的阴间，决定死磕T1了，感觉拿下的话应该也不会太差。
（但是由于前两天的《优异表现》，加上T2无法对拍，我也做好了爆零的心理准备）
稍微分析了一下发现这个T2是相当可做，二分完答案后从度数的角度入手变成了一个网络流模型，然后这个网络流还是二分图，点边级别都是 $O(m)$，这样单次check函数 $O(m\sqrt{m})$，挂个二分的log似乎就过了？

然后就开始写。
不太难写，不久就写完了。没有对拍心乱如麻…
然后就写了个环的datamaker，然后在代码里疯狂assert
自己拍自己了属于是
拍了一下发现自环的定向似乎有锅，加了个特判。
（“自环的定向”这东西本身就离谱，其实只是我的assert锅了，答案不会出错。）
然后再拍似乎就没啥问题了。

然后还有俩点，就去瞅瞅T1/3吧。

一看T3数据：k=0？大喜过望：我会并查集！
就这样十分到手。

再看T1。
越看越蒙，我甚至连它是个什么算法都没有头绪，难道真是dp？
但是这种单输入题不就是给打表准备的嘛，开始试图骗20分。
如何枚举有标号森林形态？
写个dfs，枚举当前的结点和之前哪个结点连边，然后与每片森林最多连一条边，整个带撤销并查集就可以了。比想象中好写不少。
要是无标号我恐怕就真不会了，似乎得从重心入手，可能得树哈希？
n<=10跑的飞快，8s就把我的表打出来了。
填到数组里一交20分到手=v=。
为了让我的代码显得厚重一点还把暴搜贴进去不调用一起交上去了。

然后还有一个多小时。
又又又又检查了一下T2，然后实在没有事干，就去看上午回放了。
没啥大变化，几乎和去年的视频还是一样的，就是声音变成男生了，还不如女声好听，但讲课节奏能更舒服一些。
也有收获吧，把构造最小点覆盖的方法揉到网络流整理里面了，之前第一次看我没有理解那个。
再看关押犯人那个模型还是觉得不如开虚点…

题目解析

T1

科技题。
Prufer 序列我确实不会啊…
补了两个月科技，竟然又被卡科技了？
qwq
Prufer序列就是听着高大上，其实还是挺简单的。
简洁而强大，这就是优雅。

答案可以通过1号点的贡献乘n得到。
一个重要的处理技巧是枚举1号点所在的联通块大小。
套点组合数后面的式子就比较显然了。

T2

做的还是不错的。
感觉题解的建图还没有我的建图简洁

T3

真心毒瘤题。
首先是一个trick：用LCT维护圆方树。
前几天还做过一道需要这个方法的题。
然后处理那个期望的关键是：连通块数=点数-边数+环数。
然后由于期望的线性性可以分别求解（可以说把线性性用的出神入化了）。
求黑环的期望的时候需要一个容斥。然而我发现自己讲不清楚这个容斥怎么来的，就去补了一下容斥的基础。
其实它啥也不是，就是朴素容斥而已。
感觉这两天把期望和容斥这两块基础补了还是不错的。

代码

T1 forest

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
const int N=5e3+100;
const int M=2e5+100;
const int inf=1e9;int mod;
inline ll ksm(ll x,ll k){ll res(1);while(k){if(k&1) res=res*x%mod;k>>=1;x=x*x%mod;}return res;
}int n,m;ll jc[N],ni[N];
inline ll C(int n,int m){return jc[n]*ni[m]%mod*ni[n-m]%mod;
}
ll f[N],g[N],s[N],ans[N];
void init(){n=5000;jc[0]=1;for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;ni[n]=ksm(jc[n],mod-2);for(int i=n-1;i>=0;i--) ni[i]=ni[i+1]*(i+1)%mod,assert(ni[i]*jc[i]%mod==1);f[1]=1;for(int i=2;i<=n;i++) f[i]=ksm(i,i-2);g[0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++) g[i]=(g[i]+f[j]*C(i-1,j-1)%mod*g[i-j])%mod;}s[1]=0;for(int i=2;i<=n;i++){ll b=ksm(i-1,i-1);for(int j=1;j<i;j++){b=b*ni[i-1]%mod*jc[i-2]%mod;s[i]=(s[i]+1ll*j*j%mod*C(i-2,j-1)%mod*b)%mod;}}for(int i=1;i<=n;i++){for(int j=1;j<=i;j++) ans[i]=(ans[i]+s[j]*C(i-1,j-1)%mod*g[i-j])%mod;ans[i]=ans[i]*i%mod;}//printf("f: ");for(int i=1;i<=n;i++) printf("%lld ",f[i]);puts("");//printf("g: ");for(int i=1;i<=n;i++) printf("%lld ",g[i]);puts("");//printf("s: ");for(int i=1;i<=n;i++) printf("%lld ",s[i]);puts("");//printf("ans: ");for(int i=1;i<=n;i++) printf("%lld ",ans[i]);puts("");return;
}signed main(){freopen("forest.in","r",stdin);freopen("forest.out","w",stdout);//debug("%d\n",(int)sizeof(mi)/1024/1024);int T=read();mod=read();init();while(T--){printf("%lld\n",ans[read()]);}return 0;
}
/*
4 3
1 2 1 1
2 3 1 1
3 1 1 1 
*/

T2 euler

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
const int N=4e4+100;
const int M=2e5+100;
const int inf=1e9;
const double eps=1e-10;int n,m;int s,t,tot;
struct node{int to,nxt,cap;
}p[M<<1];
int fi[N],cur[N],cnt;
inline void addline(int x,int y,int c){p[++cnt]=(node){y,fi[x],c};fi[x]=cnt;
}
inline void add(int x,int y,int c){//printf("add: %d-> %d cap=%d\n",x,y,c);addline(x,y,c);addline(y,x,0);
}
int bel[N];
queue<int>q;
int bfs(){fill(bel,bel+1+tot,0);bel[s]=1;q.push(s);while(!q.empty()){int now=q.front();q.pop();//printf("now=%d\n",now);for(int i=cur[now]=fi[now];~i;i=p[i].nxt){int to=p[i].to;if(bel[to]||!p[i].cap) continue;bel[to]=bel[now]+1;q.push(to);}}return bel[t];
}
int dfs(int x,int lim){if(!lim||x==t) return lim;int res(0);for(int &i=cur[x];~i;i=p[i].nxt){int to=p[i].to;if(bel[to]!=bel[x]+1) continue;int add=dfs(to,min(lim,p[i].cap));res+=add;lim-=add;p[i].cap-=add;p[i^1].cap+=add;if(!lim) break;}if(!res) bel[x]=-1;return res;
}
int dinic(){int flow(0),tmp(0);while(bfs()){//ok;while((tmp=dfs(s,inf))) flow+=tmp;}//printf("flow=%d\n",flow);return flow;
}int fa[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}int du[N];
int u[N],v[N],v1[N],v2[N];
int que[N<<1],num;
bool check(int k){k=que[k];//printf("check: k=%d\n",k);memset(fi,-1,sizeof(fi));cnt=-1;tot=m+n;s=++tot;t=++tot;for(int i=1;i<=m;i++){add(s,i,1);if(v1[i]<=k) add(i,v[i]+m,1);if(v2[i]<=k) add(i,u[i]+m,1);}for(int i=1;i<=n;i++){if(du[i]&1) return false;add(i+m,t,du[i]/2);}return dinic()==m;
}int x[N],y[N];
int ans[N],top;
void oula(int x,int frm){for(int i=fi[x];~i;i=fi[x]){int to=p[i].to;fi[x]=p[i].nxt;oula(to,p[i].cap);}if(frm) ans[++top]=frm;return;
}signed main(){freopen("euler.in","r",stdin);freopen("euler.out","w",stdout);n=read();m=read();for(int i=1;i<=n;i++) fa[i]=i;//int block=n;for(int i=1;i<=m;i++){u[i]=read();v[i]=read();v1[i]=read();v2[i]=read();du[u[i]]++;du[v[i]]++;que[++num]=v1[i];que[++num]=v2[i];if(find(u[i])!=find(v[i])){fa[find(u[i])]=find(v[i]);//block--;}}int id(0);for(int i=1;i<=n;i++){if(!du[i]) continue;if(!id) id=find(i);else if(id!=find(i)){//assert(0);//debug("NIE\n");puts("NIE");return 0;}}sort(que+1,que+1+num);num=unique(que+1,que+1+num)-que-1;que[num+1]=que[num]+1;//check(num+1);return 0;int st=1,ed=num+1;while(st<ed){int mid=(st+ed)>>1;if(check(mid)) ed=mid;else st=mid+1;}if(st==num+1){//assert(0);//debug("NIE\n");puts("NIE");return 0;}check(st);//int mx(0);for(int i=1;i<=m;i++){for(int j=fi[i];~j;j=p[j].nxt){int to=p[j].to;if(to==s||p[j].cap) continue;to-=m;//if(u[i]==v[i]) mx=max(mx,min(v1[i],v2[i]));//else if(to==u[i]) mx=max(mx,v2[i]);//else mx=max(mx,v1[i]);if(to==u[i]){				x[i]=v[i],y[i]=u[i];}else{				//assert(to==v[i]);x[i]=u[i],y[i]=v[i];}}//assert(x[i]);}//debug("mx=%d ans=%d\n",mx,que[st]);//assert(mx==que[st]);memset(fi,-1,sizeof(fi));cnt=-1;for(int i=1;i<=m;i++) addline(x[i],y[i],i);for(int i=1;i<=n;i++){if(du[i]){oula(i,0);break;}}if(top!=m){//assert(0);puts("NIE");return 0;}printf("%d\n",que[st]);while(top) printf("%d ",ans[top--]);return 0;
}
/*
4 3
1 2 1 1
2 3 1 1
3 1 1 1 
*/

T3 graph

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
const int N=6e5+100;
const int M=2e5+100;
const int inf=1e9;
const int mod=998244353;inline ll ksm(ll x,ll k){ll res(1);while(k){if(k&1) res=res*x%mod;k>>=1;x=x*x%mod;}return res;
}int n,m;
int id,E,o,k;int tr[N][2],sum[N],val[N],f[N],rev[N];
inline bool nroot(int x){return tr[f[x]][0]==x||tr[f[x]][1]==x;
}
inline bool which(int x){return tr[f[x]][1]==x;
}
inline void pushup(int x){if(x) sum[x]=sum[tr[x][0]]+sum[tr[x][1]]+val[x];return;
}
inline void Rev(int x){if(x){rev[x]^=1;swap(tr[x][0],tr[x][1]);}
}
inline void pushdown(int x){if(rev[x]){rev[x]=0;Rev(tr[x][0]);Rev(tr[x][1]);}
}
inline void rotate(int x){int fa=f[x],gfa=f[fa];int d=which(x),son=tr[x][d^1];f[x]=gfa;if(nroot(fa)) tr[gfa][which(fa)]=x;f[fa]=x;tr[x][d^1]=fa;if(son){f[son]=fa;}tr[fa][d]=son;pushup(fa);pushup(x);
}
int zhan[N];
inline void splay(int x){int y(x),top(0);zhan[++top]=y;while(nroot(y)) zhan[++top]=y=f[y];while(top) pushdown(zhan[top--]);for(int fa;fa=f[x],nroot(x);rotate(x)){if(nroot(fa)) which(fa)==which(x)?rotate(fa):rotate(x);}return;
}
inline void access(int x){for(int y=0;x;y=x,x=f[x]){splay(x);tr[x][1]=y;pushup(x);}
}
inline void makeroot(int x){access(x);splay(x);Rev(x);
}
inline int findroot(int x){access(x);splay(x);while(pushdown(x),tr[x][0]) x=tr[x][0];return x;
}
inline void split(int x,int y){makeroot(x);access(y);splay(y);
}
inline void link(int x,int y){makeroot(x);makeroot(y);f[x]=y;
}
inline void cut(int x,int y){split(x,y);f[x]=tr[y][0]=0;pushup(y);
}
int a[N],num;
void dfs(int x){if(!x) return;pushdown(x);dfs(tr[x][0]);a[++num]=x;dfs(tr[x][1]);return;
}
inline void add(int x,int y){num=0;if(findroot(x)!=findroot(y)) link(x,y),++E;else{split(x,y);if(sum[y]) return;++E;int now=++id;val[id]=sum[id]=1;dfs(y);for(int i=1;i<num;i++) cut(a[i],a[i+1]);for(int i=1;i<=num;i++) link(now,a[i]);return;}
}
ll w[N],b[N];
ll jc[N],ni[N];
inline ll C(int n,int m){return jc[n]*ni[m]%mod*ni[n-m]%mod;
}
void init(){jc[0]=1;for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;ni[n]=ksm(jc[n],mod-2);for(int i=n-1;i>=0;i--) ni[i]=ni[i+1]*(i+1)%mod;//assert(ni[i]*jc[i]%mod==1);ll bas=ksm(ksm(n,k),mod-2);for(int x=0;x<=n;x++){w[x]=ksm(n-x,k)*bas%mod;//printf("x=%d w=%lld\n",x,w[x]);}return;
}
inline ll B(int x){if(b[x]!=-1) return b[x];ll res(0);for(int i=0;i<=x;i++){res=(res+((i&1)?-1:1)*C(x,i)*w[i]%mod+mod)%mod;}//printf("x=%d b=%lld\n",x,res);return b[x]=res;
}int lst(0);
ll now;
signed main(){freopen("graph.in","r",stdin);freopen("graph.out","w",stdout);id=n=read();m=read();k=read();o=read();init();memset(b,-1,sizeof(b));now=n*(w[1]+o*B(1))%mod;//printf("---%lld %lld+%d*%lld\n",w[1]+o*B(1),w[1],o,B(1));while(m--){int x=read()^lst,y=read()^lst;//printf("(%d %d)\n",x,y);if(x==y){printf("%d\n",lst);continue;}add(x,y);if(num) now=(now+w[num]+o*B(num))%mod;lst=(now-E*(w[2]+o*B(2))%mod+mod)%mod;//printf("  E=%d num=%d now=%lld\n",E,num,now);printf("%d\n",lst);}return 0;
}
/*
4 3
1 2 1 1
2 3 1 1
3 1 1 1 
*/