LOJ 2882. 「JOISC 2014 Day4」两个人的星座

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

LOJ 2882. 「JOISC 2014 Day4」两个人的星座

对于任意两个凸多边形相离，一定可以找到一条直线将它们分在平面的两个区域

而对于三角形的情况更为特殊

分析可以发现，很难直接枚举三角形外直线计算，而对于任意的两个合法的三角形，在其6点中较近的4个点中

一定可以从两个三角形中各选一个点，连出两条交错的合法的分界线，例如下图

那么可以考虑枚举这样的一条直线，即确定了两个分界线上的端点，然后从两个半平面内选出不同颜色的点

直接枚举，然后 \(O(n)\) 数出这样的点，复杂度为 \(O(n^3)\)

显然可以想到枚举一个顶点，然后对于其他极角排序，旋转另一个点，同步统计半平面内的点个数，复杂度为 \(O(n^2\log n)\)

实现上，可以枚举一个点，尺取一个半平面内的点

#include<bits/stdc++.h>
using namespace std;
using ll=int64_t;
enum{N=3010};
int n,X[N],Y[N],I[N],C[N],c,s[2][3],i;
double T[N];
ll ans;
ll E(int j,int k){ return 1ll*(X[j]-X[i])*(Y[k]-Y[i])-1ll*(Y[j]-Y[i])*(X[k]-X[i]); }

int main(){
	for(int i=scanf("%d",&n);i<=n;++i) scanf("%d%d%d",X+i,Y+i,C+i);
	for(i=1;i<=n;++i) {
		c=0;
		memset(s,0,sizeof s);
		for(int j=1;j<=n;++j) if(i!=j) I[++c]=j,T[j]=atan2(Y[j]-Y[i],X[j]-X[i]),s[0][C[j]]++;
		sort(I+1,I+n,[&](int x,int y){ return T[x]<T[y]; });
		int p=1;
		for(int j=1;j<n;++j) {
			while(E(I[j],I[p])>=0) {
				s[0][C[I[p]]]--,s[1][C[I[p]]]++;
				p=p%c+1;
				if(p==j) break;
			}
			ans+=1ll*s[0][(C[i]+1)%3]*s[0][(C[i]+2)%3]*s[1][(C[I[j]]+1)%3]*s[1][(C[I[j]]+2)%3];
			s[1][C[I[j]]]--,s[0][C[I[j]]]++;
		}
	}
	cout<<ans/2;
}

一个更好的写法是把在 \(y\) 轴以下的点中心对称上来，统计时每跨过一个点改变一次

#include<bits/stdc++.h>
using namespace std;
enum{N=3010};
int n,X[N],Y[N],C[N],c,s[2][3],i,j,d,a,b,x,y;
int64_t ans;
struct Node{
	int x,y,d,c;
	Node(){}
	Node(int p,int q,int r) {
		x=p,y=q,c=r,d=0;
		if(y<0||(x<0&&y==0)) d=1,x=-x,y=-y; 
		s[d][c]++;
	}
} A[N];
struct cmp{ int operator () (const Node &a,const Node &b){ return 1ll*a.x*b.y<1ll*a.y*b.x; }};
int main(){
	for(i=scanf("%d",&n);i<=n;++i) scanf("%d%d%d",X+i,Y+i,C+i);
	for(i=1;i<=n;++i) {
		memset(s,c=0,sizeof s),a=(C[i]+1)%3,b=(a+1)%3;
		for(j=1;j<=n;++j) if(i!=j) A[++c]=Node(X[j]-X[i],Y[j]-Y[i],C[j]);
		for(sort(A+1,A+n,cmp()),j=1;j<n;++j) {
			s[A[j].d][c=A[j].c]--,x=(c+1)%3,y=(x+1)%3;
			for(d=0;d<2;++d) ans+=1ll*s[d][a]*s[d][b]*s[!d][x]*s[!d][y];
			s[!A[j].d][c]++;
		}
	}
	cout<<ans/4;
}

「JOISC 2020 Day3」收获

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

「JOISC 2020 Day3」收获

~~分类讨论.jpg~~

分析一棵苹果树被不断摘掉的过程，找到第一个摘它的人 \(i\)

此后，每次摘它的人，就是 \(i\) 前面第一个距离它 \(\ge C\) 的人，不妨设其为 \(nxt_i\)

显然， \(i,nxt_i\) 的关系，会构成基环内向树森林，每条内向边有一个权值 \(w_i\)

容易 \(O(n)\) 尺取得到 \(nxt_i,w_i\) ，考虑选择环上的一个点 \(u\) ，断开 \(u\) 对应的内向边，得到一棵树

处理得到环长 \(len_u\) ，令 \(dis_u=w_u\) ，树上每个点的 \(dis_v=dis_{nxt_v}+w_v\)

考虑一棵苹果树被第一次摘的情况，用一个二元组表示 \((v,t)\) ，即被 \(v\) 在 \(t\) 时刻摘掉

我们认为是苹果树在基环内向树上走

1.苹果树不跨过 \(u\) 时的贡献

此时相当于每个 \((v,t)\) 在往根节点走，贡献来自每个查询 \((x,d)\) 的子树

即满足 \(v\in subtree_x,dis_v-dis_x+t\leq d\)

离散之后可以用简单的询问离线+ \(dfs\) 作差+树状数组解决

\[ \ \]

2.跨过 \(u\) ，先将苹果树的贡献移动到 \(last\) 上，变为 \((last,t'=t+dis_v)\)

对于每个询问，显然必须满足 \(x\) 在环上

我们也可以令 \(d'=d-(len_u-dis_v)\) ，同样将 \(x\) 移动到 \(last\) 上

此时只需要考虑每个 \(t'\) 对于 \(d'\) 的贡献

按照 \(len_u\) ，我们可以将 \(t',d'\) 分段，每段都是 \([i\cdot len_u,(i+1)\cdot len_u)\) 的形式

2-1.对于不是同一段内的，每个 \(t'\) 的对于 \(d'\) 的贡献次数就是段编号之差

2-2.同一段内，就是满足 \(t'\leq d'\) 且 \(t'\mod len_u\leq d'\mod len_u\) 的个数

将所有 \(d',t'\) 排序后依次处理，容易通过参数分离处理2-1

对于2-2，将 \(t'\mod len_u\) 离散后可以用树状数组处理

Loj Submission

空间复杂度为 \(O(n)\) ，时间复杂度为 \(O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
ll rd(){
    char c;ll s=0;
    while(c=getchar(),c<48);
    do s=(s<<1)+(s<<3)+(c^'0');
    while(c=getchar(),c>47);
    return s;
}
enum{N=200010};
int n,m,q,nxt[N],L,C,C2,A[N*2],B[N],id[N],incir[N];
vector <int> E[N],G[N];
ll H[N],dis[N],H2[N],len[N],ans[N];
void dfs(int u){
    for(int i:E[u]) H[++C]=dis[u]+i;
    vector <int> tmp;
    for(int v:G[u]) {
        if(id[v]==id[u]) continue;
        tmp.pb(v),id[v]=id[u];
        dis[v]+=dis[u],dfs(v);
    }
    G[u]=tmp;
}

struct Node{ ll d; int id; };
vector <Node> Q[N],que;
vector <ll> upd;
struct BIT{
    int s[N],n;
    void Init(int m){ n=m,memset(s,0,(n+1)<<2); }
    void Add(int p,int x) { while(p<=n) s[p]+=x,p+=p&-p; }
    int Que(int p) {
        int res=0;
        while(p) res+=s[p],p-=p&-p;
        return res;
    }
} T,X;

// dfs作差处理情况1
void dfs2(int u){
    for(Node &i:Q[u]) {
        // 如果满足查询点在环上，就要加入2-1,2-2的计算
        if(incir[u]) {
            ll d=i.d-(len[id[u]]-dis[u]);
            if(d>=0) que.pb((Node){d,i.id});
        }
        // dfs作差-1
        ans[i.id]-=T.Que(i.d=upper_bound(H+1,H+C+1,dis[u]+i.d)-H-1);
    }
    for(int i:E[u]) T.Add(lower_bound(H+1,H+C+1,dis[u]+i)-H,1),upd.pb(dis[u]+i);
    for(int v:G[u]) dfs2(v);
    // dfs作差+1
    for(Node i:Q[u]) ans[i.id]+=T.Que(i.d);
}

int main(){
    n=rd(),m=rd(),L=rd(),C=rd();
    rep(i,0,n-1) A[i]=rd(),A[i+n]=A[i]+L;
    rep(i,0,m-1) B[i]=rd();
    int C_=C%L,p=0;
    // 尺取预处理i,nxt[i],w[i]
    rep(i,n,n*2-1) {
        while(p<i && A[i]-A[p+1]>=C_) p++;
        nxt[i-n]=p%n,G[p%n].pb(i-n);
        dis[i-n]=C-C_+A[i]-A[p];
    }
    p=0;
    // 预处理(v,t)
    rep(i,0,m-1) {
        while(p<n*2-1 && B[i]+L>=A[p+1]) p++;
        E[p%n].pb(B[i]+L-A[p]);
    }
    C=0;
    // 断环构建树
    rep(i,0,n-1) id[i]=-2;
    rep(i,0,n-1) if(id[i]==-2) {
        int u=i;
        for(;~id[u];u=nxt[u]) id[u]=-1;
        id[u]=u,len[u]=dis[u],incir[u]=1;
        for(int v=nxt[u];v!=u;v=nxt[v]) len[u]+=dis[v],incir[v]=1;
        dfs(u);
    }
    sort(H+1,H+C+1),T.Init(C=unique(H+1,H+C+1)-H-1);
    // 离线询问，权值离散
    rep(i,1,q=rd()) {
        int u=rd()-1; ll d=rd();
        Q[u].pb((Node){d,i});
    }
    rep(i,0,n-1) if(id[i]==i) {
        que.clear(),upd.clear();
        dfs2(i);
        sort(upd.begin(),upd.end()),sort(que.begin(),que.end(),[&](Node x,Node y){ return x.d<y.d; });
        C2=0;
        for(ll x:upd) H2[++C2]=x%len[i];
        sort(H2+1,H2+C2+1),X.Init(C2=unique(H2+1,H2+C2+1)-H2-1);
        auto it=upd.begin();
        ll s=0,c=0;
        for(Node &q:que) {
            while(it!=upd.end() && *it<=q.d) 
                X.Add(lower_bound(H2+1,H2+C2+1,*it%len[i])-H2,1),s+=*(it++)/len[i],c++;
            // 参数分离处理2-1
            ans[q.id]+=q.d/len[i]*c-s;
            // 树状数组查询2-2
            ans[q.id]+=X.Que(upper_bound(H2+1,H2+C2+1,q.d%len[i])-H2-1);
        }
    }
    rep(i,1,q) printf("%lld\n",ans[i]);
}

「JOISC 2020 Day3」星座 3 (dp)

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

「JOISC 2020 Day3」星座 3 (dp)

考虑根据 \(A_i\) 的值建立笛卡尔树，此时平面被划分为个矩形空间

下称选择一个点为保留一个星星

具体的，对于笛卡尔树上的节点 \((u,l,r)\) ，它的矩形就是父节点矩形以下，且满足 \(x\in[l,r],y>A_u\) 的部分

可以用一个线段树来查询矩形内部的点，线段树上每个节点维护 \(y_{max}\) ，每次剥掉 \(y_{max}>A_u\) 的部分

复杂度为均摊 \(O(n\log n)\)

\[ \ \]

观察笛卡尔树的树形，容易发现，

1.笛卡尔树左右子树的矩形之间不会产生贡献

2.每个节点对应的矩形区间内最多选择一个点

3.如果一个节点 \((u,l,r)\) 的祖先中有一个 \(x_i\in[l,r]\) 的点选择了，那么自己的矩形内不能选择点

那么令 \(dp_{u,i}\) 表示父节点传下来的点 \(x=i\) 时， \(u\) 子树内的答案

对于 \(i\in[l,r]\) 的情况，可以直接将儿子的值合并，加上自己区间内部的权值总和 \(C_i\)

对于 \(i\not \in[l,r]\) 的情况，这一部分答案相同

可以从自己子区间内选择一个点 \((x_i,y_i,c_i)\) 下传，此时沿用上面合并得到的 \(dp\) 值

\(outans=\min\{dp_{x_i}+sum-c_i\}\)

如何实现这个奇怪的 \(dp\) 过程？

考虑子树的区间不交，因此对于 \((u,l,r)\) ，只维护 \(l,r\) 内部的答案，对于 \(i\not \in[l,r]\) 的部分额外记录一个值 \(dp_u\)

考虑用一棵静态的线段树维护 \(dp\) ，线段树上存储 \(i\in[l,r]\) 的答案

合并左右儿子时，两个儿子的区间不交

因此，实际上答案就是将 \(dp_{ls}\) 加到 \([u,r]\) 上，将 \(dp_{rs}\) 加到 \([l,u]\) 上

处理出 \(sum\) 之后，区间修改 \([l,r]\) 的答案，对于 \(dp_u\) 直接按照上面的方法枚举 \((x_i,y_i,c_i)\) 来计算即可

复杂度为 \(O(n\log n)\)

int n,A[N];
struct SegFinder{
	vector <Pii> V[N];
	int s[N<<2];
	void Build(int p,int l,int r){
		if(l==r) {
			sort(V[l].begin(),V[l].end());
			s[p]=V[l].empty()?0:V[l].back().first;
			return;
		}
		int mid=(l+r)>>1;
		Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
		s[p]=max(s[p<<1],s[p<<1|1]);
	}
	void Get(int p,int l,int r,int ql,int qr,int x,vector <Pii> &Res){
		if(s[p]<x) return;
		if(l==r) {
			while(!V[l].empty() && V[l].back().first>=x) Res.pb(mp(l,V[l].back().second)),V[l].pop_back();
			s[p]=V[l].empty()?0:V[l].back().first;
			return;
		}
		int mid=(l+r)>>1;
		if(ql<=mid) Get(p<<1,l,mid,ql,qr,x,Res);
		if(qr>mid) Get(p<<1|1,mid+1,r,ql,qr,x,Res);
		s[p]=max(s[p<<1],s[p<<1|1]);
	}
} Finder;

int ls[N],rs[N],stk[N],top,mk[N];
int rt[N];
ll dp[N],s[N<<2],t[N<<2];
ll Que(int p,int l,int r,int ql,int qr){
	if(ql<=l && r<=qr) return s[p];
	int mid=(l+r)>>1; ll res=1e18;
	if(ql<=mid) cmin(res,Que(p<<1,l,mid,ql,qr));
	if(qr>mid) cmin(res,Que(p<<1|1,mid+1,r,ql,qr));
	return res+t[p];
}

void Upd(int p,int l,int r,int ql,int qr,ll x){
	if(ql<=l && r<=qr) {
		s[p]+=x,t[p]+=x;
		return;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) Upd(p<<1,l,mid,ql,qr,x);
	if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
	s[p]=min(s[p<<1],s[p<<1|1])+t[p];
}

// 线段树内存储的是 如果父节点有下传下来的答案
// dp 存储没有父节点下传的答案

void Solve(int p,int l,int r){
	vector <Pii> V; Finder.Get(1,1,n,l,r,A[p]+1,V);
	// 拿出我的决策矩形

	if(l<p) Solve(ls[p],l,p-1);
	if(p<r) Solve(rs[p],p+1,r);
	if(rs[p]) Upd(1,1,n,l,p,dp[rs[p]]);
	if(ls[p]) Upd(1,1,n,p,r,dp[ls[p]]);
	ll sum=0;
	for(Pii i:V) sum+=i.second;
	if(sum) Upd(1,1,n,l,r,sum); 
	// 如果父节点有下传，那么自己必须被清空
	// 否则考虑选择一个下传下去，这样就能得到 没有父节点下传时的值
	dp[p]=Que(1,1,n,l,r);
	for(Pii i:V) cmin(dp[p],Que(1,1,n,i.first,i.first)-i.second);
}

int main(){
	n=rd();
	rep(i,1,n) {
		A[i]=rd();
		while(top && A[stk[top]]<=A[i]) ls[i]=stk[top--];
		stk[++top]=i;
	}
	top=0;
	drep(i,n,1) {
		while(top && A[stk[top]]<A[i]) rs[i]=stk[top--];
		stk[++top]=i;
	}
	rep(i,1,n) mk[ls[i]]=mk[rs[i]]=1;
	rep(_,1,rd()) {
		int x=rd(),y=rd(),c=rd();
		Finder.V[x].pb(mp(y,c));
	}
	Finder.Build(1,1,n);
	rep(i,1,n) if(!mk[i]) {
		Solve(i,1,n);
		printf("%lld\n",dp[i]);
		return 0;
	}
}

「JOISC 2020 Day4」首都城市

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

「JOISC 2020 Day4」首都城市

题目大意：给定一棵树，每个点有颜色

求选择一个最小的颜色集合，使得这些颜色的点能够构成一个连通块

容易发现，选取这个颜色就必须将这个颜色连通路径上的所有其它颜色选掉

但是要纠正一个：

并不是选取的这个颜色的连通路径上的颜色就行

因为选取另一个颜色，可能导致不在当前连通路径上的其它颜色也需要被选取

\[ \ \]

这样的关系构成一个有向图，一条边表示选了 \(u\) 就选 \(v\)

因此可以考虑 \(\text{tarjan}\) 强连通缩点，由于最终我们选择强连通分量一定没有出边（否则不优）

因此可以线性统计答案，问题在于如何建立这个图

首先考虑如何将这个连通路径提取出来，一种简单的办法是：找到这个颜色所有点的 \(\text{LCA}\) ，路径就可以表示为 \(\text{LCA}\) 到所有点路径的并

Solution1

树剖线段树完成路径连边

点数为 \(O(n)\) ，边数为 \(O(n\log ^2n)\)

Solution2

倍增连边

点数边数均为 \(O(n\log n)\)

Solution3

离线，用类似 \(\text{tarjan LCA}\) 的方式，维护一个并查集

每次并查集的父亲关系改变时，新建节点，即可完成一个类似可持久化的操作

如果再用 \(\text{tarjan}\) 预处理 \(\text{LCA}\) ，复杂度/点数/边数就为 \(O(n\alpha(n))\)

#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
char buf[200000],*p1,*p2;
#define getchar() (((p1==p2)&&(p2=(p1=buf)+fread(buf,1,200000,stdin))),*p1++)
int rd(){
	int s=0;static char c;
	while(c=getchar(),c<48);
	do s=(s<<1)+(s<<3)+(c^'0');
	while(c=getchar(),c>47);
	return s;
}

const int N=2e5+10,INF=1e9+10,K=N*3.5;

int n,k,m;
int A[N],L[N],F[N],C[N],Fir[N],I[N];
vector <int> G[N],V[N];
struct Edge{ 
	int to,nxt; 
} e[K*2];
int head[K],ecnt;
void AddEdge(int u,int v){
	if(u==v) return;
	e[++ecnt]=(Edge){v,head[u]};
	head[u]=ecnt;
}

int Find1(int x){ return F[x]==x?x:F[x]=Find1(F[x]); }
void pre_dfs(int u,int f){
	F[u]=u;
	if(!Fir[A[u]]) Fir[A[u]]=u;
	if(--C[A[u]]==0) L[A[u]]=Find1(Fir[A[u]]);
	for(int v:G[u]) if(v!=f) pre_dfs(v,u);
	F[u]=f;
}

Pii Find(int x){
	if(F[x]==x) return mp(F[x],I[x]);
	Pii t=Find(F[x]);
	return AddEdge(++m,t.second),AddEdge(m,I[x]),F[x]=t.first,mp(F[x],I[x]=m);
}

void dfs(int u,int f){
	F[u]=u,I[u]=A[u];
	for(int v:G[u]) if(v!=f) dfs(v,u);
	for(int v:V[u]) AddEdge(A[v],Find(v).second);
	F[u]=f;
}

int t[K],low[K],ins[K],stk[K],top,dfn;
int ans=1e9,vis[N],out[K];
void dfs(int u){
	t[u]=low[u]=++dfn,ins[stk[++top]=u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!t[v]) dfs(v),cmin(low[u],low[v]);
		else if(ins[v]) cmin(low[u],t[v]);
	}
	if(low[u]==t[u]){
		int fl=1,tmp=top;
		for(int v=-1;v!=u;){
			v=stk[top--];
			for(int i=head[v];i;i=e[i].nxt) if(!ins[e[i].to]) { fl=0; break; }
		}
		rep(i,top+1,tmp) ins[stk[i]]=0;
		if(fl) {
			int res=0;
			rep(i,top+1,tmp) {
				int x=stk[i];
				if(x<=k && !vis[x]) vis[x]=1,res++;
			}
			rep(i,top+1,tmp) if(stk[i]<=k) vis[stk[i]]=0;
			if(res) cmin(ans,res-1);
		}
	}
}

int main(){
	n=rd(),k=rd();
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),G[v].pb(u);
	}
	rep(i,1,n) C[A[i]=rd()]++;
	pre_dfs(1,0);
	rep(i,1,n) V[L[A[i]]].pb(i);
	m=k;
	dfs(1,0);
	rep(i,1,k) if(!t[i]) dfs(i);
	printf("%d\n",ans);
	fprintf(stderr,"Vertices =%d \nEdges =%d\n",m,ecnt);
}

「JOISC 2020 Day4」传奇团子师傅 (假模拟退火)

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

「JOISC 2020 Day4」传奇团子师傅 (假模拟退火)

感觉每次想写模拟退火，调着调着就不知道变成什么东西了

首先是分析原图，每个方案对应选择三个点，不同的方案之间显然存在排斥关系

将这些关系建立成边，问题就转化为一个 一般图最大独立集 问题

~~这怎么搞得定。。~~

因此考虑退火，每次操作随机选择一个点，检查周围的点是否选择，数一下如果自己被选，要弹掉的点的个数

同普通的退火，一开始温度高不停随机

到了后面就直接变成选择答案不劣的方案（也就是交换两个点），事实证明这样的效率比较高

但是直接随机容易随机到选过的点，需要稍微加速一下

具体的，退火每若干次为一轮，每轮随机一个排列

在排列中从左到右找到前面 \(L\) 个未选点，然后在 \(L\) 个点中随机若干次进行决策

我是直接暴力bitset存答案的，但是效率好像还可以

因为是跑一个点调一次参数的，前面的代码都没存。。。

tips:代码对于不同数据需要修改前面三行的常量

const int N=510,M=N*N/2,INF=1e9+10;
const char infile[]="5.in",outfile[]="output_05.txt";
const int MAX=48620;

int n,m,C;
char s[N][N];
int chk(char x){ return x=='P' || x=='G'; }
struct Node{
    int x,y,t;
} R[M];
bitset <M> Ansmap,Nowmap;
int ans,now;

int z[4][2]={{0,1},{1,0},{-1,-1},{-1,1}};
char S[]="-|\\/";
vector <int> G[N][N],E[M];

struct Naive_Simulator{
    ~Naive_Simulator(){
        cerr<<"!"<<endl;
        rep(i,1,C) if(Ansmap[i]) s[R[i].x][R[i].y]=S[R[i].t];
        rep(i,1,n) puts(s[i]+1);
    }
    int P[M],D[M],F[M],PC,counter,lst,L;
    void Work(db T,db d,db End,int delta) {
        while(T>End && ans<MAX) {
            if(++counter%4000==0) {
                cerr<<ans<<' '<<T<<endl;
            }
            if(counter%500==0) random_shuffle(D+1,D+C+1),lst=1;
            PC=0;
            rep(i,lst,C) if(!Nowmap[D[i]]) {
                P[++PC]=D[i];
                lst=i;
                if(PC>=L) break;
            }
            if(PC<L) {
                lst=1;
                PC=0;
                rep(i,lst,C) if(!Nowmap[D[i]]) {
                    P[++PC]=D[i];
                    lst=i;
                    if(PC>=L) break;
                }
            }
            rep(kase,1,50) {
                int u,v;
                u=P[rand()%PC+1],v=P[rand()%PC+1];
                if(u==v || Nowmap[u]) {
                    kase--;
                    continue;
                }
                int cnt=0;
                for(int v:E[u]) cnt+=Nowmap[v];
                if(cnt-delta<=T) {
                    Nowmap[u]=1;
                    for(int v:E[u]) Nowmap[v]=0;
                    now+=1-cnt;
                } 
                if(kase%5==0 && now>ans) ans=now,Ansmap=Nowmap;
            }
            T*=d;
        }
    }
    void Simulate(){
        //srand(114514);
        //srand(1919810);
        srand(time(NULL));
        now=0,Nowmap.reset();
        counter=0,lst=1,L=200;
        rep(i,1,C) D[i]=i;
        rep(kase,1,10) Work(2,0.95,1e-2,1);
        Work(0.99,0.99993,1e-8,2);
        Nowmap=Ansmap,now=ans;
        Work(0.99,0.99999,0,1);
        return;
    }

    Naive_Simulator(){
        freopen(infile,"r",stdin),freopen(outfile,"w",stdout);
        n=rd(),m=rd();
        rep(i,1,n) scanf("%s",s[i]+1);
        rep(i,1,n) rep(j,1,m) if(!chk(s[i][j])) {
            s[i][j]='W';
            rep(d,0,3) if(chk(s[i+z[d][0]][j+z[d][1]]) && chk(s[i-z[d][0]][j-z[d][1]]) && s[i+z[d][0]][j+z[d][1]]!=s[i-z[d][0]][j-z[d][1]]) {
                R[++C]=(Node){i,j,d};
                G[i][j].pb(C);
                G[i+z[d][0]][j+z[d][1]].pb(C);
                G[i-z[d][0]][j-z[d][1]].pb(C);
            }
        }
        rep(i,1,n) rep(j,1,m) rep(k,0,G[i][j].size()-1) rep(l,k+1,kend) {
            E[G[i][j][k]].pb(G[i][j][l]);
            E[G[i][j][l]].pb(G[i][j][k]);
        }
        Simulate();
    }
} Solver;

int main(){ ; }

LOJ 6719. 「300iq Contest 2」数仙人掌加强版 (集合幂级数)

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

LOJ 6719. 「300iq Contest 2」数仙人掌加强版 (集合幂级数)

前置知识：集合幂级数的 \(\ln ,\exp\)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
enum{N=20,M=1<<18|10,P=998244353};
struct U{
	int x;
	U(){} U(int x):x(x){}
	inline void operator += (const U &t){ x+=t.x,x>=P&&(x-=P); }
	inline void operator -= (const U &t){ x-=t.x,x<0&&(x+=P); }
	inline U operator * (const U &t){ return U(static_cast<unsigned long long>(x)*t.x%P); }
}I[N],F[M][N],H[M][N];
int n,m,G[N],C[M],B[M];
void FWT(int f) {
	for(int i=1;i<m;i<<=1) {
		for(int l=0;l<m;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				if(f==1) rep(d,1,n) F[j+i][d]+=F[j][d];
				else rep(d,1,n) F[j+i][d]-=F[j][d];
			}
		}
	}
}
void Exp(U *a){
	static U b[N];
	rep(i,0,n-1) b[i]=a[i+1]*(i+1);
	rep(i,0,n-1) {
		U t=b[i];
		rep(j,1,i) t+=a[j]*b[i-j];
		a[i+1]=t*I[i+1];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	if(n==1) return puts("1"),0;
	for(int x,y;m--;) scanf("%d%d",&x,&y),x--,y--,G[x]|=1<<y,G[y]|=1<<x;
	I[0]=I[1]=1,m=1<<n;
	rep(i,0,n-1) B[1<<i]=i;
	rep(i,2,n) I[i]=U(P-P/i)*I[P%i];
	rep(i,1,m-1) C[i]=C[i&(i-1)]+1;
	rep(st,0,n-1) {
		H[1<<st][st]=1;
		rep(S,0,m-1) rep(i,st,n-1) if(H[S][i].x) {
			for(int T=G[i]&~S;T;T&=T-1) 
				H[S|(T&-T)][B[T&-T]]+=H[S][i];
			if(G[i]&(1<<st)) F[S][C[S]]+=H[S][i]*I[1+(C[S]>2)];
			H[S][i]=0;
		}
	}
	FWT(1);
	for(int i=1;i<m;i<<=1){
		for(int l=0;l<m;l+=i*2) for(int j=l;j<l+i;++j) {
			rep(k,1,n) F[j+i][k]-=F[j][k];
			Exp(F[j+i]+1);
			rep(k,1,n) F[j+i][k]+=F[j][k];
		}
	}
	FWT(-1),printf("%d\n",F[m-1][n].x);
}

LOJ6729. 点双连通生成子图计数 (集合幂级数)

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

LOJ6729. 点双连通生成子图计数 (集合幂级数)

基础：由子图的集合幂级数取 \(\ln\) 可以得到连通子图的集合幂级数，可以参考?

根据点双连通的定义，我们先求得连通子图的集合幂级数

然后考虑枚举每个节点 \(i\) ，把所有删去 \(i\) 之后不连通的方案去掉

具体实现上，可以把所有包含 \(i\) 的项提出，删除 \(i\) 之后取 \(\ln\) 得到连通的方案数，然后替换回去

每次取 \(\ln\) 的复杂度为 \(O(n^22^n)\) ，因此总复杂度为 \(O(n^32^n)\)

常数优化：每次实际上只会修改包含 \(i\) 的项，不需要每次都把多项式莫比乌斯反演回去

刚开始进行一次莫比乌斯变换之后

每次可以直接从前缀和的作差得到这一项除了 \(i\) 以外的位置累和之后的结果，然后直接对于形式幂级数取 \(\ln\) ，具体实现见代码

注意去掉 \(i\) 后，占位数量 \(-1\)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
const int N=20,M=1<<18|3,P=998244353;
struct U{
	int x;
	U(){} U(int x):x(x){}
	inline void operator += (const U &t){ x+=t.x,x>=P&&(x-=P); }
	inline void operator -= (const U &t){ x-=t.x,x<0&&(x+=P); }
	inline U operator * (const U &t){ return U(static_cast<unsigned long long>(x)*t.x%P); }
} I[N],F[M][N],b[N];
int n,m,G[N],C[M],Pow[N*N];
void FWT(int f){
	for(int i=1;i<m;i<<=1) for(int l=0;l<m;l+=i*2) 
		for(int j=l;j<l+i;++j) if(f==1) rep(d,1,n) F[j+i][d]+=F[j][d];
		else rep(d,1,n) F[j+i][d]-=F[j][d];
}
void Ln(U *a){
	rep(i,0,n-1) {
		U t=0;
		rep(j,0,i-1) t+=b[j]*a[i-j];
		b[i]=a[i+1]*(i+1),b[i]-=t;
	}
	rep(i,1,n) a[i]=b[i-1]*I[i];
}
int main() {
	scanf("%d%d",&n,&m);
	for(int u,v;m--;) scanf("%d%d",&u,&v),u--,v--,G[u]|=1<<v,G[v]|=1<<u;
	m=1<<n,I[0]=I[1]=1;
	rep(i,1,m-1) C[i]=C[i&(i-1)]+1;
	rep(i,2,n) I[i]=U(P-P/i)*I[P%i];
	rep(i,Pow[0]=1,N*N-1) Pow[i]=Pow[i-1]*2%P;
	rep(i,1,m-1) {
		int c=0;
		rep(j,0,n-1) if(i&(1<<j)) c+=C[G[j]&i];
		F[i][C[i]]=Pow[c/2];
	}
	FWT(1);
	rep(i,1,m-1) Ln(F[i]);
    // 先取一次ln得到连通子图的集合幂级数
	for(int i=1;i<m;i<<=1){
		for(int l=0;l<m;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				rep(k,1,n) F[j+i][k]-=F[j][k]; // 前缀和作差得到
				Ln(F[j+i]+1); // 取出自己后大小-1
				rep(k,1,n) F[j+i][k]+=F[j][k];
			}
		}
	}
	FWT(-1);
	printf("%d\n",F[m-1][n].x);
}

「JOI 2021 Final」地牢 3

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

「JOI 2021 Final」地牢 3

判定无解

无解即： \(\exists i\in[S,T-1],A_i>U\)

是一个简单的区间最值问题

\[\ \]

\(O(nm)\)

关于用单调队列之类的东西维护每个点权值的方法这里就不提了

形式化地，我们把一层层点放到数轴上，令 \(X_i=\sum_{j<i}A_j\)

在数轴上坐标每 \(+1\) 消耗一点能量，我们要从 \(X_S\) 走到 \(X_T\)

考虑每个点的情况，不妨看做是用 \(B_i\) 去覆盖 \((X_S,X_T]\) ，求最小权值

发现对于 \(B_i\) ，它能够合法覆盖的区间一定是 \((X_i,X_i+U]\)

暴力地，可以直接让 \(B_i\) 更新这段区间的最小权值，然后暴力求和

\[\ \]

进一步分析每个 \(B_i\) 覆盖的区间，可以发现是合法区间 \((X_i,X_i+U]\) 中的某一连续段 \((L_i,R_i]\)

而 \(L_i\) 取决于 \(B_i\) 前面第一个 \(B_{pre}<B_i\) ， \(R_i\) 取决于后面第一个 \(B_{nxt}\leq B_i\)

关于 \(pre,nxt\) 的求解显然只是一个单调栈解决

得到 \((L_i,R_i]\) 简单的描述

\(L_i=\max\{X_i,X_{pre}+U\}\)

\(R_i=\min\{X_i+U,X_{nxt}\}\)

(ps:这样求得的 \(L_i\) 不一定 \(<R_i\) )

暴力枚举即可 \(O(n)\) 查询

\[ \ \]

\(T_i=n+1\) 从这里开始需要一些数据结构？

考虑倒着从 \(n\) 到 \(1\) 计算每一个 \(S_i\) 的答案

发现在刚插入 \(i\) 的时候， \(pre_i\) 还未出现，可以看做 \(-\infty\) ， \(nxt_i\) 已经确定

当 \(pre_i\) 出现时可以重新进行一次插入

每次插入可以用三元组表示 \((i,pre,nxt)\) ，为了便于叙述这里 \(pre,nxt\) 直接是坐标

考虑对于 \(L_i,R_i\) 进行参数分离计算，首先要考虑何时满足 \(L_i<R_i\)

显然条件就是 \(nxt-pre>U\)

\(\displaystyle L_i=\max\{X_i,X_{pre}+U\}=X_{pre}+\max\{X_i-X_{pre},U\}\)

\(\displaystyle R_i=\min\{X_i+U,X_{nxt}\}=X_i+\min\{U,X_{nxt}-X_i\}\)

\(\displaystyle Answer=\sum_{nxt-pre>U} (R_i-L_i)\cdot B_i\)

离线询问，离散之后可以用树状数组维护上述式子，对于不合法部分不要加入即可

\[\ \]

\[ \ \]

\(O(n\log n)\)

上面已经能计算 \(T_i=n+1\) 的询问，考虑将 \(S,T\) 转化为 \(T_{i}=n+1\) 的问题

如果直接 \(S,T\) 相减显然不合法，不妨找到在 \((S,n+1)\) 的方案中，覆盖的 \(T\) 的点 \(T'\)

\((S,n+1)-(T',n+1)\) 会抵消掉在 \(S\) 的方案中 \(T\) 右边的部分，而 \((X_{T'},X_T]\) 显然仍然是由 \(B_{T'}\) 覆盖，补回来即可

由此完成分离操作，而根据上面区间覆盖的定义， \(T'\) 实际上就是 \((X_T-U,X_T]\) 中最小的 \(B_i\)

所有操作都可以 \(O(n\log n)\) 完成

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10,INF=1e9+10;

int n,m,A[N],B[N],nxt[N],stk[N],top,C;
ll ans[N],X[N],H[N];
struct Node{ int U,k,id; };
vector <Node> Q[N];
vector <int> G[N];
struct BIT{
	ll s[N];
	void Add(int p,ll x){ 
		while(p<=C) s[p]+=x,p+=p&-p; 
	}
	ll Que(int p){
		ll res=0;
		while(p) res+=s[p],p-=p&-p;
		return res;
	}
} T1,T2;
// T1维护式子中含U项的和
// T2维护式子中常数和

struct MaxTree{
	int s[N<<2],bit;
	void Build(){
		for(bit=1;bit<=n+1;bit<<=1) ;
		rep(i,1,n) s[bit+i]=A[i];
		drep(i,bit,1) s[i]=max(s[i<<1],s[i<<1|1]);
	}
	int Que(int l,int r){
		if(l==r) return s[l+bit];
		int res=0;
		for(l+=bit-1,r+=bit+1;l^r^1;l>>=1,r>>=1){
			if(~l&1) cmax(res,s[l^1]);
			if(r&1) cmax(res,s[r^1]);
		}
		return res;
	}
} Max;
struct MinTree{
	int s[N<<2],bit;
	int Min(int x,int y){ return mp(B[x],x)<mp(B[y],y)?x:y; }
	void Build(){
		B[0]=1e9;
		for(bit=1;bit<=n+1;bit<<=1) ;
		rep(i,1,n) s[bit+i]=i;
		drep(i,bit,1) s[i]=Min(s[i<<1],s[i<<1|1]);
	}
	int Que(int l,int r){
		if(l==r) return s[l+bit];
		int res=0;
		for(l+=bit-1,r+=bit+1;l^r^1;l>>=1,r>>=1){
			if(~l&1) res=Min(res,s[l^1]);
			if(r&1) res=Min(res,s[r^1]);
		}
		return res;
	}
} Min;
// Min 用于寻找T'

void Add(int i,ll pre,ll nxt,int k){
	int p=lower_bound(H+1,H+C+1,X[i]-pre)-H,r=lower_bound(H+1,H+C+1,nxt-pre)-H;
	// -L
	T1.Add(p,-B[i]*k), T1.Add(r,B[i]*k);
	T2.Add(p,k*B[i]*(X[i]-pre)), T2.Add(r,-k*B[i]*(X[i]-pre));
	// +R 
	p=lower_bound(H+1,H+C+1,nxt-X[i])-H;
	T1.Add(1,k*B[i]),T1.Add(p,-k*B[i]);
	T2.Add(p,k*(nxt-X[i])*B[i]),T2.Add(r,-k*(nxt-X[i])*B[i]);
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) A[i]=rd(),X[i+1]=X[i]+A[i];
	rep(i,1,n) B[i]=rd();
	drep(i,n+1,1) {
		while(top && B[stk[top]]>=B[i]) G[i].pb(stk[top--]);
		nxt[i]=stk[top],stk[++top]=i;
	}
	Min.Build(),Max.Build();
	rep(i,1,m) {
		int S=rd(),T=rd(),U=rd();
		if(Max.Que(S,T-1)>U){ ans[i]=-1; continue; }
		H[++C]=U,Q[S].pb((Node){U,1,i});
		int l=lower_bound(X+1,X+n+2,X[T]-U)-X; cmax(l,S);
		int t=Min.Que(l,T);
		ans[i]+=(X[T]-X[t])*B[t];
		Q[t].pb((Node){U,-1,i});
	}
	sort(H+1,H+C+1),C=unique(H+1,H+C+1)-H-1;
	drep(i,n,1){
		Add(i,-1e9,X[nxt[i]],1);
		for(int j:G[i]) Add(j,-1e9,X[nxt[j]],-1),Add(j,X[i],X[nxt[j]],1);
		for(Node j:Q[i]){
			int p=lower_bound(H+1,H+C+1,j.U)-H;
			ans[j.id]+=j.k*(j.U*T1.Que(p)+T2.Que(p));
		}
	}
	rep(i,1,m) printf("%lld\n",ans[i]);
}

[BZOJ4331] [JSOI2012]越狱老虎桥

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

[BZOJ4331] [JSOI2012]越狱老虎桥

题意: 在任意加入一条边的情况下，求割一条边使图不从1联通的最小割边的最大值

首先根据题目的意思，可以下对这个无向图中进行边双联通分量 缩点

建出一棵边双生成树，树边即为原图的割边，树边带权

割掉双联通分量内部的边显然没有意义，所以忽略掉他们，下文所提的均是树上节点和边

在不额外加边的情况下，而割掉树边会使子树内部的点断开

在加入边的情况下，若加入一条 \(1-u\) 的边，则形成了一个 \(1-u\) 的环，环是无法通过割开一条边断开的

而连接树上两个节点 \((u,v)\) 的情况，把图展开后，就会发现，就是把 \(u,v\) 路径上所有的点都缩进了同一个环

此时断掉环上的边显然不合法，而不在环上的边，只需要随便断掉一条，就能让一个点不连通

也就是说，答案是 (去掉某个点对 \((u,v)\) 路径上的所有边，剩下的边中最小值) 的最大值

设答案为 \(ans\)

这个问题实际上等价于所有的 \(e\in E,w(e)\leq ans\) 的边无法被一条路径完全覆盖

做法1:

考虑二分答案，把每条 \(e\in E,w(e)\leq ans\) 的边的权值设为1，求出直径长度判断是否可以用一条路径完全覆盖即可

复杂度为 \(O(n\log n)\)

做法2:

实际上这个问题就是 (选择了合法的3条边中边权的最大值) 的最小值

对于当前节点 \(u\) ，实际合法情况有

1.选择了一条祖先的边，和2条儿子岔开的边

2.选择了3条垂下的岔开的边，这个合并时比较诡异可以看代码

\(\text{dp}\) 维护即可，复杂度为 \(O(n)\)

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=5e5+10,INF=1e9+10;

int n,m;
struct Edge{
	int to,nxt,w;
} e[N*6];
int head[N],ecnt;
void AddEdge(int u,int v,int w) {
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}
#define erep(u,i) for(int i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)

int low[N],t[N],id[N],scc,dfn;
int stk[N],top;
void dfs(int u,int f) {
	low[u]=t[u]=++dfn;
	stk[++top]=u;
	erep(u,i) if(v!=f) {
		if(!t[v]) dfs(v,u),cmin(low[u],low[v]);
		else cmin(low[u],t[v]);
	}
	if(low[u]==t[u]){
		int v; ++scc;
		do v=stk[top--],id[v]=scc;
		while(v!=u);
	}
}

int head2[N];
void AddEdge2(int u,int v,int w) {
	e[++ecnt]=(Edge){v,head2[u],w};
	head2[u]=ecnt;
}
#define erep2(u,i) for(int i=head2[u],v=e[i].to,w=e[i].w;i;i=e[i].nxt,v=e[i].to,w=e[i].w)

int ans=INF;
int dp[N][4],tmp[4],g[N];

void dfs1(int u,int f) {
	dp[u][0]=0,dp[u][1]=dp[u][2]=dp[u][3]=INF;
	erep2(u,i) if(v!=f) {
		g[v]=min(g[u],w),dfs1(v,u);
		memset(tmp,63,sizeof tmp);
		rep(j,0,3) {
			cmin(tmp[j],dp[u][j]);
			if(j<3) cmin(tmp[j+1],max(dp[u][j],w));
			rep(k,0,3-j) cmin(tmp[j+k],max(dp[u][j],dp[v][k]));
		}
		rep(j,0,3) dp[u][j]=tmp[j];
	}
	cmin(ans,dp[u][3]);
	cmin(ans,max(g[u],dp[u][2]));
}


int main(){
	n=rd(),m=rd();
	rep(i,1,m) {
		int u=rd(),v=rd(),w=rd();
		AddEdge(u,v,w),AddEdge(v,u,w);
	}
	dfs(1,0);
	rep(u,1,n) erep(u,i) if(id[u]!=id[v]) AddEdge2(id[u],id[v],e[i].w);
	g[id[1]]=INF,dfs1(id[1],0);
	printf("%d\n",ans==INF?-1:ans);
}

[CSP-S 2020 T3] 动物园 (拓扑排序)

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

[CSP-S 2020 T3] 动物园 (拓扑排序)

很难考虑每个操作的顺序，但由于操作比较简单，可以直接考虑每个操作贡献的权值

一个操作的权值可以定义为：每次这个操作执行之后后，后面所有的乘法操作的积

如果没有递归，只需要倒序枚举一次调用情况，就能知道所有的权值

对于递归的情况，显然函数之间的递归关系构成一张拓扑图，可以考虑预处理出每个操作的乘法操作之积

对于所有的函数，同样能得到一个权值，接下来的操作只需要把每个存在递归的函数不断将权值向下传给子函数

如果把最终的调用序列看做一个主函数，那么对于这个操作实际也是一样的做法

即：倒序枚举一次累积，然后乘上自己的权值下传即可

Tips: 最后加入贡献时，注意先将所有数的权值乘上全局乘法倍数，然后再依次处理每个加法操作

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
int rd(){ 
	int s=0,f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e5+10,P=998244353;

int n,m;
int A[N],T[N],H[N]; 
// A为原数组，T为乘法积，H为函数调用权值
int O[N],X[N],Y[N];
int B[N*11],C,L[N],R[N],ind[N];
int Q[N],QL,QR;

int main() {
	//freopen("call.in","r",stdin),freopen("call.out","w",stdout);
	rep(i,1,n=rd()) A[i]=rd();
	m=rd()+1; // 令m+1号为主函数
	rep(i,1,m) {
		O[i]=i<m?rd():3,T[i]=1;
		if(O[i]==1) X[i]=rd(),Y[i]=rd();
		else if(O[i]==2) T[i]=rd();
		else {
			L[i]=C+1,R[i]=C+=rd();
			rep(j,L[i],R[i]) ind[B[j]=rd()]++;
		}
	}
	rep(i,QL=1,m) if(!ind[i]) Q[++QR]=i;
	while(QL<=QR) {
		int u=Q[QL++];
		if(O[u]==3) rep(j,L[u],R[u]) if(--ind[B[j]]==0) Q[++QR]=B[j];
	}
	drep(k,m,1){
		int u=Q[k];
		if(O[u]==3) rep(j,L[u],R[u]) T[u]=1ll*T[u]*T[B[j]]%P;
	}
	
	rep(i,H[m]=1,n) A[i]=1ll*A[i]*T[m]%P;
	rep(k,1,m) {
		int u=Q[k],x=1;
		drep(j,R[u],L[u]){
			int v=B[j];
			H[v]=(H[v]+1ll*x*H[u])%P;
			x=1ll*x*T[v]%P;
		}
		if(O[u]==1) A[X[u]]=(A[X[u]]+1ll*H[u]*Y[u])%P;
	}
	rep(i,1,n) printf("%d ",A[i]); puts("");
}

LOJ 2882. 「JOISC 2014 Day4」两个人的星座

「JOISC 2020 Day3」收获

「JOISC 2020 Day3」星座 3 (dp)

「JOISC 2020 Day4」首都城市

Solution1

Solution2

Solution3

「JOISC 2020 Day4」传奇团子师傅 (假模拟退火)

LOJ 6719. 「300iq Contest 2」数仙人掌 加强版 (集合幂级数)

LOJ6729. 点双连通生成子图计数 (集合幂级数)

「JOI 2021 Final」地牢 3

判定无解

\(O(nm)\)

\(T_i=n+1\) 从这里开始需要一些数据结构？

\(O(n\log n)\)

[BZOJ4331] [JSOI2012]越狱老虎桥

[CSP-S 2020 T3] 动物园 (拓扑排序)

LOJ 6719. 「300iq Contest 2」数仙人掌加强版 (集合幂级数)