建设保障房网站首页,垂直 网站开发,官方网站aspcms,wordpress图片存储方案前言
day11 期望#xff1a;406030130 实际#xff1a;4003070 rnk16
挂大分了。。 T2树边不加双向#xff1a;60-0。 这什么伞兵bug啊#xff01; 整体状态也不太好#xff0c;T2死磕无果。 T1看出正解结果写不出来拉插#xff0c;乐。
题目解析
T1 网格序列406030130 实际4003070 rnk16
挂大分了。。 T2树边不加双向60-0。 这什么伞兵bug啊 整体状态也不太好T2死磕无果。 T1看出正解结果写不出来拉插乐。
题目解析
T1 网格序列grid
一开始看就不太想做的一个题。 因为对自己计数方面的能力还是不太自信。。。 还是喜欢树算法awa。 死磕T2N年后回来发现这个题有点纸老虎拉插一下不就能过吗awa 然后…拉插柿子长啥样来着… 然后就for循环40分跑路了。
关键性质一个序列合法当且仅当行最大值的最大值等于列最大值的最大值。 有了这个就不难列出答案的式子了 ans∑i1k(in−(i−1)n)(im−(i−1)m)ans\sum_{i1}^k(i^n-(i-1)^n)(i^m-(i-1)^m)ansi1∑k(in−(i−1)n)(im−(i−1)m) 这个东西显然是一个 nm1nm1nm1 次的多项式。 直接连续选点快速插值即可 O(n)O(n)O(n) 求单点值。 求函数值的时候快速幂会炸需要线性筛把 xn,xmx^n,x^mxn,xm 这两个东西当成积性函数筛出来还是完全积性的呢 然后就做完了。 确实是不太难的一道题唉。
T2 交换游戏exchange
今日死因了属于是。 一直在想dfs序转二维数点问题但是那样的话二维线段树直接就带上两个log了。 然后就一直在寻找各种优化到方法后来整了一个差分加二维线段树合并的神奇科技拿掉了一个log却带上了18倍常数。 呵呵还不如个log。
正解感觉和NOI那道轻重边异曲同工都是利用染色来进行题意的转化。 题意从另一个角度来看就是一棵树一条边的两端点在另一棵树上形成的链之间的边是需要在考虑范围的。 然后用染色满足反过来的限制dsu on tree 维护。 确实巧妙。
T3 树的删除delete
别说这个题我还真想到LCT了。 但是我也就只看出操作1可以当成换根对于维护排名还是很茫然。 按照题解的思路这个“链”可以恰好用类似access维护虚实边的方式维护。 确实不太好想到…但是既然觉得是LCT其实应该从那个算法反过来出发想想的。
感叹出题人真是用心良苦。
代码
T1
#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 N2e6100;
const int M1e6100;
const int mod998244353;int n,m,k;inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}ll nmi[N],mmi[N];
int vis[N],prime[N],tot;
void init(){nmi[1]mmi[1]1;for(int i2,onm2;io;i){if(!vis[i]){prime[tot]i;nmi[i]ksm(i,n);mmi[i]ksm(i,m);}for(int j1;jtotprime[j]o/i;j){int nowprime[j];nmi[now*i]nmi[now]*nmi[i]%mod;mmi[now*i]mmi[now]*mmi[i]%mod;vis[now*i]1;if(i%now0) break;}}return;
}
ll f[N];
ll jc[N],ni[N],pre[N],suf[N];
ll lagrange(int n,ll *y,int k){//if(kn) return y[k];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;pre[0]1;for(int i1;in;i) pre[i]pre[i-1]*(k-imod)%mod;suf[n1]1;for(int in;i1;i--) suf[i]suf[i1]*(k-imod)%mod;ll ans(0);for(int i1;in;i){ll addy[i]*pre[i-1]%mod*suf[i1]%mod*ni[i-1]%mod*ni[n-i]%mod;//printf(i%d add%lld y%lld pre%lld suf%lld ni%lld %lld\n,i,add,y[i],pre[i-1],suf[i1],ni[i-1],ni[n-i]);if((n-i)1) ans(ansmod-add)%mod;else ans(ansadd)%mod;}return ans;
}signed main(){freopen(grid.in,r,stdin);freopen(grid.out,w,stdout);nread();mread();kread();init();int onm2;for(int i1;io;i){f[i](f[i-1](nmi[i]-nmi[i-1]mod)*(mmi[i]-mmi[i-1]mod))%mod;}printf(%lld\n,lagrange(o,f,k));return 0;
}
/*
*/
T2
#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 N2e5100;
const int M1e6100;
const int mod998244353;int n,m,k;
bool jd0;#define mid ((lr)1)
#define ls (k1)
#define rs (k1|1)
struct node{int lc,rc,sum;
}tr[N2];
node merge(node a,node b){if(!a.sum) return b;else if(!b.sum) return a;else return (node){a.lc,b.rc,a.sumb.sum-(a.rcb.lc)};
}
int laz[N2];
inline void tag(int k){tr[k].lctr[k].rc0;tr[k].sum1;laz[k]0;
}
inline void pushdown(int k){if(laz[k]-1) return;laz[k]-1;tag(ls);tag(rs);return;
}
inline void pushup(int k){tr[k]merge(tr[ls],tr[rs]);return;
}
void change(int k,int l,int r,int p,int w){if(lr){tr[k].lctr[k].rcw;tr[k].sum1;return;}pushdown(k);if(pmid) change(ls,l,mid,p,w);else change(rs,mid1,r,p,w);pushup(k);
}
node ask(int k,int l,int r,int x,int y){if(xy) return (node){-1,-1,0};if(xlry) return tr[k];pushdown(k);if(ymid) return ask(ls,l,mid,x,y);else if(xmid) return ask(rs,mid1,r,x,y);else return merge(ask(ls,l,mid,x,y),ask(rs,mid1,r,x,y));
}
struct tree2{vectorintv[N];void addline(int x,int y){v[x].push_back(y);v[y].push_back(x);}int hson[N],siz[N],dep[N],top[N],tim,fa[N],dfn[N],pos[N];void dfs1(int x,int f){siz[x]1;dep[x]dep[f]1;fa[x]f;for(int to:v[x]){if(tof) continue;dfs1(to,x);siz[x]siz[to];if(siz[to]siz[hson[x]]) hson[x]to; }return;}void dfs2(int x,int tp){top[x]tp;dfn[tim]x;pos[x]tim;if(hson[x]) dfs2(hson[x],tp);for(int to:v[x]){if(tofa[x]||tohson[x]) continue;dfs2(to,to);}return;}inline void add(int x){if(jd) printf( add:%d\n,x);change(1,1,n,pos[x],1);return;}inline int Lca(int x,int y){while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]) swap(x,y);xfa[top[x]];}if(dep[x]dep[y]) swap(x,y);return y;}inline node find(int x,int anc,int op){if(jd) printf(find: x%d anc%d op%d\n,x,anc,op);node res(node){-1,-1,0};while(top[x]!top[anc]){resmerge(ask(1,1,n,pos[top[x]],pos[x]),res);if(jd){printf( merge: %d %d (%d %d %d)\n,top[x],x,res.lc,res.rc,res.sum);}xfa[top[x]];}resmerge(ask(1,1,n,pos[anc]op,pos[x]),res);if(jd){node oask(1,1,n,pos[anc]op,pos[x]);printf( o: (%d %d %d)\n,o.lc,o.rc,o.sum);printf( merge: %d %d (%d %d %d)\n,anc,x,res.lc,res.rc,res.sum);}return res;}inline int query(int x,int y){int lcaLca(x,y);node ufind(x,lca,0),vfind(y,lca,1);if(jd){printf(query: (%d %d) lca%d u:(%d %d %d) v:(%d %d %d)\n,x,y,lca,u.lc,u.rc,u.sum,v.lc,v.rc,v.sum);}return u.sumv.sum-(u.lcv.lc);}
}t2;
int ans[N],u[N],v[N];
struct tree1{vectorintv[N];void addline(int x,int y){v[x].push_back(y);v[y].push_back(x);}int hson[N],siz[N],dep[N],top[N],tim,fa[N],dfn[N],pos[N];void dfs1(int x,int f){siz[x]1;dep[x]dep[f]1;fa[x]f;for(int to:v[x]){if(tof) continue;dfs1(to,x);siz[x]siz[to];if(siz[to]siz[hson[x]]) hson[x]to; }return;}void dfs2(int x,int tp){top[x]tp;dfn[tim]x;pos[x]tim;if(hson[x]) dfs2(hson[x],tp);for(int to:v[x]){if(tofa[x]||tohson[x]) continue;dfs2(to,to);}return;}void solve(int x,int kep){for(int to:v[x]){if(tofa[x]||tohson[x]) continue;solve(to,0);}if(hson[x]) solve(hson[x],1);t2.add(x);for(int to:v[x]){if(tofa[x]||tohson[x]) continue;for(int ipos[to];ipos[to]siz[to]-1;i){int nowdfn[i];t2.add(now);}}if(fa[x]) ans[x]t2.query(x,fa[x]);if(!kep){tag(1);if(jd) printf(clear\n\n);}return;}
}t1;signed main(){freopen(exchange.in,r,stdin);freopen(exchange.out,w,stdout);nread();for(int i1;in;i){u[i]read(),v[i]read();t1.addline(u[i],v[i]);}for(int i1;in;i){int xread(),yread();t2.addline(x,y);}t2.dfs1(1,0);t2.dfs2(1,1);t1.dfs1(1,0);t1.dfs2(1,1);t1.solve(1,0);for(int i1;in;i){if(t1.fa[v[i]]u[i]) swap(u[i],v[i]);printf(%d ,ans[u[i]]-1);}return 0;
}
/*
4
1 2
1 3
1 4
1 2
2 3
3 4
*/
T3
#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 N4e5100;
const int M1e6100;
const int mod998244353;int n,m,k;
bool jd0;int mx,s[N];
inline void add(int p,int w){if(jd) printf( val%d\n,p);for(;pmx;pp-p) s[p]w;
}
inline int ask(int p){int res(0);for(;p;p-p-p) ress[p];return res;
}int tr[N][2],f[N],siz[N],bot[N],top[N],rev[N],val[N];
void print(){for(int i1;in;i) printf(i%d ls%d rs%d fa%d siz%d bot%d top%d\n,i,tr[i][0],tr[i][1],f[i],siz[i],bot[i],top[i]);puts();
}
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){siz[x]siz[tr[x][0]]siz[tr[x][1]]1;bot[x]tr[x][1]?bot[tr[x][1]]:x;top[x]tr[x][0]?top[tr[x][0]]:x;}
}
inline void Rev(int x){if(x){swap(tr[x][0],tr[x][1]);swap(bot[x],top[x]);rev[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){assert(x);int top(0),y(x);zhan[top]x;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;
}
int now;
void access(int x,int op1){//assert(x);if(jd) printf(\naccess: %d\n,x);int orix;for(int y(0);x;yx,xf[x]){assert(x);splay(x);if(jd) printf( del: %d siz%d\n,x,siz[x]);add(val[bot[x]],-siz[x]);int otr[x][1];if(o){ //splay(o);//printf( o%d bot%d siz%d\n,o,bot[o],siz[o]);if(jd) printf( add: %d siz%d\n,o,siz[o]);add(val[bot[o]],siz[o]);}//splay(x);tr[x][1]y;pushup(x);}splay(ori);if(op) val[ori]now;//assert(nowbot[now]);if(jd) printf( add: %d siz%d\n,ori,siz[ori]);add(val[op?top[ori]:bot[ori]],siz[ori]);if(jd) puts();
}
void makeroot(int x){access(x);splay(x);Rev(x);
}
vectorintv[N];
void dfs(int x,int fa){f[x]fa;for(int to:v[x]){if(to!fa) dfs(to,x);}return;
}
inline int rnk(int x){splay(x);int oask(val[bot[x]]-1);if(jd) printf(o%d bot%d siz%d\n,o,bot[x],siz[tr[x][1]]);osiz[tr[x][1]];return o1;
}
char ss[100];
signed main(){freopen(delete.in,r,stdin);freopen(delete.out,w,stdout);//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);nread();mread();mxnm;nown;for(int i1;in;i){int xread(),yread();v[x].push_back(y);v[y].push_back(x);}dfs(n,0);for(int i1;in;i){val[i]i;bot[i]top[i]i;siz[i]1;add(val[i],1);}for(int i1;in;i){access(i,0);//print();}for(int i1;im;i){int opread(),xread();if(op1){//val[x]now;makeroot(x);}else printf(%d\n,rnk(x));if(jd) printf(op%d x%d\n,op,x);if(jd) print();}return 0;
}
/*
4
1 2
1 3
1 4
1 2
2 3
3 4
*/
