云优化 网站建设,响应式做的比较好的网站,最好的搭建网页的平台,商城网站建设如何交谈文章目录前言考场题目解析T1T2T3代码T1 forestT2 eulerT3 graph前言
130pts 2010010 终于没有挂分#xff01; 开心#xff01; 然而今天的题确实过于阴间…三道题几乎都没法写暴力#xff0c;爆零场了属于是。 我这个分数都能到rnk4勒。 #xff08;rnk39-rnk4#…
文章目录前言考场题目解析T1T2T3代码T1 forestT2 eulerT3 graph前言
130pts 2010010 终于没有挂分 开心 然而今天的题确实过于阴间…三道题几乎都没法写暴力爆零场了属于是。 我这个分数都能到rnk4勒。 rnk39-rnk4乐
考场
一拿题我就觉得不太妙。 T1数树题第一眼看到输入一个数输出一个数就想到应该是生成函数多项式但是不给NTT模数 难道这玩意能dp …本场满分200分。 T2看起来还挺正常的把二分写脸上了。 T3题如其名动态沙漠玩期望《毒瘤》我突然发现自己仙人掌是一道题都没做过感觉可能要LCT罢但是那个期望我也没什么想法…本场满分100分。
20min我差不多明白了本场考试的阴间决定死磕T1了感觉拿下的话应该也不会太差。 但是由于前两天的《优异表现》加上T2无法对拍我也做好了爆零的心理准备 稍微分析了一下发现这个T2是相当可做二分完答案后从度数的角度入手变成了一个网络流模型然后这个网络流还是二分图点边级别都是 O(m)O(m)O(m)这样单次check函数 O(mm)O(m\sqrt m)O(mm)挂个二分的log似乎就过了
然后就开始写。 不太难写不久就写完了。没有对拍心乱如麻… 然后就写了个环的datamaker然后在代码里疯狂assert 自己拍自己了属于是 拍了一下发现自环的定向似乎有锅加了个特判。 “自环的定向”这东西本身就离谱其实只是我的assert锅了答案不会出错。 然后再拍似乎就没啥问题了。
然后还有俩点就去瞅瞅T1/3吧。
一看T3数据k0大喜过望我会并查集 就这样十分到手。
再看T1。 越看越蒙我甚至连它是个什么算法都没有头绪难道真是dp 但是这种单输入题不就是给打表准备的嘛开始试图骗20分。 如何枚举有标号森林形态 写个dfs枚举当前的结点和之前哪个结点连边然后与每片森林最多连一条边整个带撤销并查集就可以了。比想象中好写不少。 要是无标号我恐怕就真不会了似乎得从重心入手可能得树哈希 n10跑的飞快8s就把我的表打出来了。 填到数组里一交20分到手v。 为了让我的代码显得厚重一点还把暴搜贴进去不调用一起交上去了。
然后还有一个多小时。 又又又又检查了一下T2然后实在没有事干就去看上午回放了。 没啥大变化几乎和去年的视频还是一样的就是声音变成男生了还不如女声好听但讲课节奏能更舒服一些。 也有收获吧把构造最小点覆盖的方法揉到网络流整理里面了之前第一次看我没有理解那个。 再看关押犯人那个模型还是觉得不如开虚点…
题目解析
T1
科技题。 Prufer 序列我确实不会啊… 补了两个月科技竟然又被卡科技了 qwq Prufer序列就是听着高大上其实还是挺简单的。 简洁而强大这就是优雅。
答案可以通过1号点的贡献乘n得到。 一个重要的处理技巧是枚举1号点所在的联通块大小。 套点组合数后面的式子就比较显然了。
T2
做的还是不错的。 感觉题解的建图还没有我的建图简洁
T3
真心毒瘤题。 首先是一个trick用LCT维护圆方树。 前几天还做过一道需要这个方法的题。 然后处理那个期望的关键是连通块数点数-边数环数。 然后由于期望的线性性可以分别求解可以说把线性性用的出神入化了。 求黑环的期望的时候需要一个容斥。然而我发现自己讲不清楚这个容斥怎么来的就去补了一下容斥的基础。 其实它啥也不是就是朴素容斥而已。 感觉这两天把期望和容斥这两块基础补了还是不错的。
代码
T1 forest
#includebits/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 cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N5e3100;
const int M2e5100;
const int inf1e9;int mod;
inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;k1;xx*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(){n5000;jc[0]1;for(int i1;in;i) jc[i]jc[i-1]*i%mod;ni[n]ksm(jc[n],mod-2);for(int in-1;i0;i--) ni[i]ni[i1]*(i1)%mod,assert(ni[i]*jc[i]%mod1);f[1]1;for(int i2;in;i) f[i]ksm(i,i-2);g[0]1;for(int i1;in;i){for(int j1;ji;j) g[i](g[i]f[j]*C(i-1,j-1)%mod*g[i-j])%mod;}s[1]0;for(int i2;in;i){ll bksm(i-1,i-1);for(int j1;ji;j){bb*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 i1;in;i){for(int j1;ji;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 i1;in;i) printf(%lld ,f[i]);puts();//printf(g: );for(int i1;in;i) printf(%lld ,g[i]);puts();//printf(s: );for(int i1;in;i) printf(%lld ,s[i]);puts();//printf(ans: );for(int i1;in;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 Tread();modread();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
#includebits/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 cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N4e4100;
const int M2e5100;
const int inf1e9;
const double eps1e-10;int n,m;int s,t,tot;
struct node{int to,nxt,cap;
}p[M1];
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];
queueintq;
int bfs(){fill(bel,bel1tot,0);bel[s]1;q.push(s);while(!q.empty()){int nowq.front();q.pop();//printf(now%d\n,now);for(int icur[now]fi[now];~i;ip[i].nxt){int top[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||xt) return lim;int res(0);for(int icur[x];~i;ip[i].nxt){int top[i].to;if(bel[to]!bel[x]1) continue;int adddfs(to,min(lim,p[i].cap));resadd;lim-add;p[i].cap-add;p[i^1].capadd;if(!lim) break;}if(!res) bel[x]-1;return res;
}
int dinic(){int flow(0),tmp(0);while(bfs()){//ok;while((tmpdfs(s,inf))) flowtmp;}//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[N1],num;
bool check(int k){kque[k];//printf(check: k%d\n,k);memset(fi,-1,sizeof(fi));cnt-1;totmn;stot;ttot;for(int i1;im;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 i1;in;i){if(du[i]1) return false;add(im,t,du[i]/2);}return dinic()m;
}int x[N],y[N];
int ans[N],top;
void oula(int x,int frm){for(int ifi[x];~i;ifi[x]){int top[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);nread();mread();for(int i1;in;i) fa[i]i;//int blockn;for(int i1;im;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 i1;in;i){if(!du[i]) continue;if(!id) idfind(i);else if(id!find(i)){//assert(0);//debug(NIE\n);puts(NIE);return 0;}}sort(que1,que1num);numunique(que1,que1num)-que-1;que[num1]que[num]1;//check(num1);return 0;int st1,ednum1;while(sted){int mid(sted)1;if(check(mid)) edmid;else stmid1;}if(stnum1){//assert(0);//debug(NIE\n);puts(NIE);return 0;}check(st);//int mx(0);for(int i1;im;i){for(int jfi[i];~j;jp[j].nxt){int top[j].to;if(tos||p[j].cap) continue;to-m;//if(u[i]v[i]) mxmax(mx,min(v1[i],v2[i]));//else if(tou[i]) mxmax(mx,v2[i]);//else mxmax(mx,v1[i]);if(tou[i]){ x[i]v[i],y[i]u[i];}else{ //assert(tov[i]);x[i]u[i],y[i]v[i];}}//assert(x[i]);}//debug(mx%d ans%d\n,mx,que[st]);//assert(mxque[st]);memset(fi,-1,sizeof(fi));cnt-1;for(int i1;im;i) addline(x[i],y[i],i);for(int i1;in;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
#includebits/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 cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N6e5100;
const int M2e5100;
const int inf1e9;
const int mod998244353;inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;k1;xx*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 faf[x],gfaf[fa];int dwhich(x),sontr[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]yf[y];while(top) pushdown(zhan[top--]);for(int fa;faf[x],nroot(x);rotate(x)){if(nroot(fa)) which(fa)which(x)?rotate(fa):rotate(x);}return;
}
inline void access(int x){for(int y0;x;yx,xf[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]) xtr[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){num0;if(findroot(x)!findroot(y)) link(x,y),E;else{split(x,y);if(sum[y]) return;E;int nowid;val[id]sum[id]1;dfs(y);for(int i1;inum;i) cut(a[i],a[i1]);for(int i1;inum;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 i1;in;i) jc[i]jc[i-1]*i%mod;ni[n]ksm(jc[n],mod-2);for(int in-1;i0;i--) ni[i]ni[i1]*(i1)%mod;//assert(ni[i]*jc[i]%mod1);ll basksm(ksm(n,k),mod-2);for(int x0;xn;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 i0;ix;i){res(res((i1)?-1:1)*C(x,i)*w[i]%modmod)%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);idnread();mread();kread();oread();init();memset(b,-1,sizeof(b));nown*(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 xread()^lst,yread()^lst;//printf((%d %d)\n,x,y);if(xy){printf(%d\n,lst);continue;}add(x,y);if(num) now(noww[num]o*B(num))%mod;lst(now-E*(w[2]o*B(2))%modmod)%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
*/
