atcoder-note

不能懒了。

记录一点做过的abc中的h。

abc219h

好久以前做的，记不清了，套路大概是多开一维记录还没跑到的地方。

不如贴个三维写的题解吧！

here

upd：震惊了，以前竟然在学校在本子上写过这题题解。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=310;
int n,sum=0;
struct node{
	int x,h;
}a[N];
bool cmp(node x,node y){
	return x.x<y.x;
} 
int dp[N][N][2][N];
void chmax(int &x,int y){
	if(y>x)x=y;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n;
	forn(i,2,n+1)cin>>a[i].x>>a[i].h;
	a[1].x=0;a[1].h=0;n++;
	sort(a+1,a+n+1,cmp);
	forn(i,1,n)sum+=a[i].h;
	memset(dp,-0x3f,sizeof(dp));
	int pos;
	forn(i,1,n)if(a[i].x==0&&a[i].h==0)pos=i;
	forn(i,0,n)dp[pos][pos][0][i]=dp[pos][pos][1][i]=sum;
	forn(len,2,n){
		forn(i,1,n){
			int j=i+len-1;
			if(j>n)break;
			forn(k,0,n){
				chmax(dp[i][j][0][k],dp[i+1][j][0][k]-(a[i+1].x-a[i].x)*(n-len-k+1));
				chmax(dp[i][j][0][k],dp[i+1][j][1][k]-(a[j].x-a[i].x)*(n-len-k+1));
				chmax(dp[i][j][0][k],dp[i+1][j][0][k+1]-(a[i+1].x-a[i].x)*(n-len-k)-a[i].h);
				chmax(dp[i][j][0][k],dp[i+1][j][1][k+1]-(a[j].x-a[i].x)*(n-len-k)-a[i].h);
				
				chmax(dp[i][j][1][k],dp[i][j-1][0][k]-(a[j].x-a[i].x)*(n-len-k+1));
				chmax(dp[i][j][1][k],dp[i][j-1][1][k]-(a[j].x-a[j-1].x)*(n-len-k+1));
				chmax(dp[i][j][1][k],dp[i][j-1][0][k+1]-(a[j].x-a[i].x)*(n-len-k)-a[j].h);
				chmax(dp[i][j][1][k],dp[i][j-1][1][k+1]-(a[j].x-a[j-1].x)*(n-len-k)-a[j].h);
			}
		}
	}
	cout<<max(dp[1][n][0][0],dp[1][n][1][0])<<"\n";
	return 0;
}

abc221h

题意

给定 $n,m$，对于每个 $k\in[1,n]$ 求出恰好 $k$ 个数和为 $n$ 的方案数，每个数出现次数不超过 $m$。

$m\leq n\leq5000$

做法

考虑从大到小选数，如果在纸上选数画出来是若干段，选的数为 $i$ 的段有 $i$ 条，把这个东西相邻的段之间拼起来，就得到若干条前缀线段，在 $i$ 选一些前缀线段表示 $i+1$ 和 $i$ 选的数不同了，然后清算 $i$ 的贡献，本质上也可以理解为对差分数组做dp。差分数组乘上后面元素的个数求和即为原序列的和，这是考虑差分数组对后续的影响。

然后问题转化成了选 $k$ 个数，不能有连续 $m$ 个 $0$，和为 $n$。

这个就直接dp，套个前缀和优化一下，用调和来优化是 $O(n^2\ln n)$，用循环顺序类似无限背包是 $O(n^2)$。

启发：数形结合 差分

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=5010,mod=998244353;
int n,m;
int dp[N][N],sum[N][N];
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	dp[0][0]=1;sum[0][0]=1;
	forn(i,1,n){
		forn(j,i,n){
			dp[i][j]=(dp[i][j]+sum[i-1][j-i])%mod;
			if(i-m-1>=0)dp[i][j]=(dp[i][j]-sum[i-m-1][j-i]+mod)%mod;
			dp[i][j]=(dp[i][j]+dp[i][j-i])%mod;
		}
		forn(j,0,n){
			sum[i][j]=(sum[i-1][j]+dp[i][j])%mod;
		}
	}
	forn(i,1,n){
		cout<<dp[i][n]<<"\n";
	}
	return 0;
}

abc223h

题意

$n$ 个数，$q$ 次询问，每次询问 $[l,r]$ 的数中能不能通过异或表示出 $x$。

$n\leq4\times10^5$

$q\leq 2\times 10^5$

$x< 2^{60}$

做法

一眼线性基，一种办法是直接上线段树维护，两个 $\log$，努努力过得去。

还可以离线对 $r$ 排序，对新加入 $a_r$，能成功插入的后缀线性基是单调的，二分出这个位置，暴力加，由于线性基最多 $\log$ 个元素，所以这个做法也是两个 $\log$。

正解是魔改线性基，对每一位存最大可以从哪里得到，插入的时候如果能直接插入就直接插入，不行看看能不能替换，然后类似李超树一样swap一下，继续下去。

查询的时候就比较最小值和 $l$，一个$\$log$。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=400010;
int n,m;
int a[N];
int basis[60][N],idx[60][N];
void ins(int x,int p){
	int qwq=p;
	rep(i,60){
		basis[i][p]=basis[i][p-1];
		idx[i][p]=idx[i][p-1];
	}
	fore(i,59,0){
		if((x>>i)&1){
			if(!basis[i][qwq]){
				basis[i][qwq]=x;idx[i][qwq]=p;break;
			}
			else if(p>idx[i][qwq]){
				swap(basis[i][qwq],x);swap(idx[i][qwq],p);
			}
			x^=basis[i][qwq];
		}
	}
}
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	forn(i,1,n){
		cin>>a[i];ins(a[i],i);
	}
	while(m--){
		int l,r,x;cin>>l>>r>>x;
		bool flag=1;
		fore(i,59,0){
			if((x>>i)&1){
				if(!basis[i][r]||idx[i][r]<l){
					flag=0;break;
				}
				else x^=basis[i][r];
			}
		}
		if(flag)cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

abc226h

题意

$n$ 个数，每个数是 $[l_i,r_i]$ 中随机的一个实数，问期望第 $k$ 大是多少。

做法

这位更是重量级。

容易发现， $l,r$ 都是整数，整数部分不同的两个数一定能直接比较，而且一小段中每两个数的概率都应该是相等的，所以我们将数轴划分为若干 $[A,A+1]$。

枚举最后答案在的区间（枚举 $A$），然后dp。

${\rm dp} (i,j,k)$ 表示前 $i$ 个数有 $j$ 个在 $[A,A+1]$，$k$ 个大于 $A+1$ 的概率。

然后对每个 ${\rm dp}(n,i,j)$ 要算的即为往 $[A,A+1]$ 里面撒 $i$ 个点，第 $k-j$ 大的期望。

考虑一个模型。

$[0,1]$ 里面撒 $n$ 个点，第 $k$ 大期望是多少。

考虑期望的定义，对每个 $x$ 作为结果时积分，得钦定一个 $x$，大于 $x$ 的 $(k-1)$ 个。

百度一下贝塔函数和伽马函数。写点式子推一下。

$n\binom {n-1} {k-1}\int_0^1 x^{n-k+1}(1-x)^{k-1}dx=\\ n\binom {n-1} {k-1}\frac {(n-k+1)!(k-1)!} {(n+1)!}=\frac {n!(n-k+1)!(k-1)!} {(k-1)!(n-k)!(n+1)!}=\frac {n-k+1} {n+1}=1-\frac k {n+1}$

当然你也可以不推到最后，第一步就可以直接积了。

时间复杂度 $O(n^4)$。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=55,mod=998244353;
int dp[N][N][N];
int n,k;
int l[N],r[N];
int iv[N<<1];
int ans=0;
int qpow(int n,int k){
	int ans=1;
	while(k){
		if(k&1)ans=ans*n%mod;
		n=n*n%mod;
		k>>=1;
	}
	return ans;
}
void solve(int x){
	memset(dp,0,sizeof(dp));
	dp[0][0][0]=1;
	forn(i,1,n){
		forn(j,0,n){
			forn(a,0,n){
				if(l[i]<=x){	
					dp[i][j][a]+=dp[i-1][j][a]*(min(x,r[i])-l[i])%mod*iv[r[i]-l[i]]%mod;
					dp[i][j][a]%=mod;
				}
				if(l[i]<=x&&r[i]>x&&j){
					dp[i][j][a]+=dp[i-1][j-1][a]*iv[r[i]-l[i]]%mod;
					dp[i][j][a]%=mod;
				}
				if(r[i]>x+1&&a){
					dp[i][j][a]+=dp[i-1][j][a-1]*(r[i]-max(x+1,l[i]))%mod*iv[r[i]-l[i]]%mod;
					dp[i][j][a]%=mod;
				}
			}		
		}
	}
	forn(j,0,n){
		forn(a,0,n){
			if(k-a>j||k-a<=0)continue;
			int qwq=(a-k+mod)*iv[j+1]%mod;
			qwq+=x+1;qwq%=mod;qwq*=dp[n][j][a];qwq%=mod;
			ans+=qwq;ans%=mod;
		}
	}
}
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	forn(i,0,105)iv[i]=qpow(i,mod-2);
	cin>>n>>k;
	forn(i,1,n)cin>>l[i]>>r[i];
	rep(i,101)solve(i);
	cout<<ans<<"\n";
	return 0;
}

abc231h

题意

一个 $H\times W$ 的网格，有 $n$ 个棋子，第 $i$ 个在 $(a_i,b_i)$，有代价 $c_i$。

选一些棋子使得每一行每一列都有至少一个棋子，代价最小化。

$H,W,n\leq1000$

做法

一眼网络流，介绍两个建模方式。

行和列分两侧建出一张二分图。看的出来是最大权边覆盖。类比不带权是怎么做的。

不带权就是 $H+W-{\rm maxflow}$。意思是先全选，然后二分图匹配做成一次可以少选一个，于是最大匹配。

这个无非是先每个点对答案贡献代价最小的边，然后做最大权匹配，做成一条边答案 $+w-{\rm mn}(u)-{\rm mn}(v)$。

第二种做法是我看神奇的三维写的。

他也是分两侧点，然后对每个点限制一个流量为 ${\rm deg}(i)-1$，意思是最多能 ban 掉这么多条边，然后直接跑。

不一定是最大流，但是要让费用最小。写的时候注意一下。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=2010,M=6010,inf=1e18;
int h,w,n;
int a[1010],b[1010],c[1010];
int mn[2010];
int s,t;
int cnt=1;
struct edge{
	int v,nxt,cap,cost;
}e[M<<1];
int head[N]; 
void addedge(int u,int v,int cap,int cost){
	cnt++;
	e[cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
	e[cnt].cap=cap;e[cnt].cost=cost;
	swap(u,v);cap=0;cost*=-1;
	cnt++;
	e[cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
	e[cnt].cap=cap;e[cnt].cost=cost;
} 
bool vis[N];
int dis[N],sum=0;
bool spfa(int s,int t){
	forn(i,1,t)dis[i]=inf;
	queue<int>q;
	q.push(s);vis[s]=1;dis[s]=0;
	while(!q.empty()){
		int u=q.front();q.pop();vis[u]=0;
		for(int p=head[u];p;p=e[p].nxt){
			int v=e[p].v;
			if(e[p].cap&&dis[v]>dis[u]+e[p].cost){
				dis[v]=dis[u]+e[p].cost;
				if(!vis[v]){
					q.push(v);vis[v]=1;
				}
			}
		}
	}
	return dis[t]!=inf;
}
int res=0;
int dfs(int u,int t,int in){
	if(u==t)return in;
	int out=0;
	vis[u]=1;
	for(int p=head[u];p;p=e[p].nxt){
		int v=e[p].v;
		if(!vis[v]&&e[p].cap&&dis[v]==dis[u]+e[p].cost){
			int x=dfs(v,t,min(in,e[p].cap));in-=x;
			res+=e[p].cost*x;e[p].cap-=x;e[p^1].cap+=x;out+=x;
			if(!in)break;
		}
	}
	vis[u]=0;
    if(!out)dis[u]=-1;
	return out;
}
int mcmf(int s,int t){
	int sum=0;
	while(spfa(s,t)){
		res=0;
        dfs(s,t,1e9);
        if(res>0)break;
        sum+=res;
	}
	return sum;
} 
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	memset(mn,0x3f,sizeof(mn));
	cin>>h>>w>>n;
	forn(i,1,n){
		cin>>a[i]>>b[i]>>c[i];b[i]+=h;
		mn[a[i]]=min(mn[a[i]],c[i]);
		mn[b[i]]=min(mn[b[i]],c[i]);
	}
	s=h+w+1;t=s+1;
	forn(i,1,n){
		if(c[i]<mn[a[i]]+mn[b[i]])addedge(a[i],b[i],1,c[i]-mn[a[i]]-mn[b[i]]);
	}
	forn(i,1,h)addedge(s,i,1,0);
	forn(i,1,w)addedge(i+h,t,1,0);
	int ans=0;
	forn(i,1,h+w)ans+=mn[i];
	ans+=mcmf(s,t);
	cout<<ans<<"\n"; 
	return 0;
}

abc232h

题意

有一个 $H\times W$ 的网格，构造一条从 $(1,1)$ 走到 $(a,b)$ 的路径，每个点被经过恰好一次。

$2\leq H,W\leq100$。

做法

由于当 $H,W$ 都大于 $2$ 时候一定有解，我们可以在有一个等于 $2$ 的时候特判路径，都大于 $2$ 的时候扒掉边缘一层不包含 $(a,b)$ 的，然后解决一个规模更小的子问题。

大概复杂度是三方吧。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define vpii vector<pii>
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
vpii solve(int h,int w,int a,int b){
	vpii res;
	if(h==2){
		if(a==1){
			forn(i,1,b-1){
				res.pb(m_p(1,i));
				res.pb(m_p(2,i));
			}
			res.pb(m_p(2,b));
			forn(i,b+1,w)res.pb(m_p(2,i));
			fore(i,w,b)res.pb(m_p(1,i));
		}	
		else{
			if(b==1){
				forn(i,1,w)res.pb(m_p(1,i));
				fore(i,w,1)res.pb(m_p(2,i));
			}
			else{
				forn(i,1,b-1){
					res.pb(m_p(1,i));
					res.pb(m_p(2,i));
				}
				res.pb(m_p(1,b));
				forn(i,b+1,w)res.pb(m_p(1,i));
				fore(i,w,b)res.pb(m_p(2,i));
			}
		}
	} 
	else if(w==2){
		vpii v=solve(w,h,b,a);
		rep(i,v.size())swap(v[i].fi,v[i].se);
		rep(i,v.size())res.pb(v[i]);
	}
	else{
		if(b==1||(a==h&&b==2)){
			vpii v=solve(w,h,b,a);
			rep(i,v.size()){
				int x=v[i].se,y=v[i].fi;
				res.pb(m_p(x,y));
			}
		}	
		else{
			forn(i,1,h)res.pb(m_p(i,1));
			vpii v=solve(w-1,h,b-1,h+1-a);
			rep(i,v.size()){
				int x=h+1-v[i].se,y=v[i].fi+1;
				res.pb(m_p(x,y));
			}
		}	
	}
	return res;
}
int h,w,a,b;
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>h>>w>>a>>b;
	vpii ans=solve(h,w,a,b);
	for(auto x:ans)cout<<x.fi<<" "<<x.se<<"\n";
	return 0;
}

abc233h

题意

有 $n$ 棵圣诞树，第 $i$ 棵在 $(a_i,b_i)$。

$q$ 次询问，每次查询距离 $(x,y)$ 曼哈顿距离第 $k$ 近的点距离他的曼哈顿距离是多少。

$n,a,b,q,x,y\leq 10^5$

做法

曼哈顿距离两维坐标互相影响，不好做，考虑变成切比雪夫距离。

然后二分一个答案，问题就变成判定一个矩形内有多少个点。

可以拿主席树维护，每个横坐标的前缀维护纵坐标内点的情况，典。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=300010,A=300001;
int n;
struct Point{
	int x,y;
}p[N];
vector<int>v[N];
struct node{
	int l,r;
	int sum;
}t[N*35];
int root[N]; 
int cnt=0;
void ins(int l,int r,int pre,int &cur,int p){
	t[++cnt]=t[pre];
	cur=cnt;
	t[cur].sum++;
	if(l==r)return;
	int mid=l+r>>1;
	if(p<=mid)ins(l,mid,t[pre].l,t[cur].l,p);
	else ins(mid+1,r,t[pre].r,t[cur].r,p); 
}
int qry(int l,int r,int L,int R,int ql,int qr){
	if(l>qr||r<ql)return 0;
	if(l>=ql&&r<=qr)return t[R].sum-t[L].sum;
	int mid=l+r>>1;
	return qry(l,mid,t[L].l,t[R].l,ql,qr)+qry(mid+1,r,t[L].r,t[R].r,ql,qr);
}
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n;
	forn(i,1,n){
		cin>>p[i].x>>p[i].y;int a=p[i].x+p[i].y,b=p[i].x-p[i].y;
		p[i].x=a+100001;p[i].y=b+100001;
		v[p[i].x].pb(p[i].y);
	}
	int pre=0;
	forn(i,1,A){
		int cur=0;
		for(auto x:v[i]){
			ins(1,A,pre,cur,x);
			pre=cur;
		}
		root[i]=pre;
	}
	int q;cin>>q;
	while(q--){
		int x,y,k;cin>>x>>y>>k;
		int a=x+y+100001,b=x-y+100001;
		int l=0,r=A;
		while(l<=r){
			int mid=l+r>>1;
			int l0=max(a-mid-1,0ll),r0=min(a+mid,A);
			int l1=max(b-mid,1ll),r1=min(b+mid,A);
			if(qry(1,A,root[l0],root[r0],l1,r1)<k)l=mid+1;
			else r=mid-1;
		}
		cout<<r+1<<"\n";
	}
	return 0;
}

abc234h

记不得了。把以前写的贴上来。

一看就像计算几何。但是可以暴力。

我们把每个点 $(x_i,y_i)$ 放到一个包 $(\lfloor \frac {x_i} k \rfloor,\lfloor \frac {y_i} k \rfloor)$中。发现符合条件的点一定在包$(\lfloor \frac {x_i} k \rfloor\pm1,\lfloor \frac {y_i}k \rfloor\pm1)$ 中。

先来证明一个含 $x$ 个点的包中符合条件的配对数是 $O(x^2)$ 级别的。

上界显然。接下来证明下界。

对于任意一个边长小于等于 $\frac k {\sqrt 2}$ 的子矩形，其中任意一对都可以满足条件，而且一个$k\times k$ 的矩形可以拆成 $4$ 个这样的矩形，如果这个包里有 $4n$ 个点，至少有一个小矩形有 $n$ 个点，于是下界证明完毕。

记 $B(X,Y)$ 为包 $(X,Y)$ 中点的个数。 $f(X,Y)$ 为 $B(X,Y)$ 内部配对数。

因为有 $\sum\limits_{X,Y} f(X,Y)\leq M$，所以 $\sum\limits_{X,Y} B(X,Y)^2\leq N+M$

最多要考虑的答案对数有$\sum\limits_{X,Y}\sum\limits_{l=-1}^1\sum\limits_{m=-1}^1B(X,Y)B(X+l,Y+m)$ 因为有上面证的上界。所以易得 $B(X,Y)B(X+l,Y+m)\leq\frac {B(X,Y)^2+B(X+l,Y+m)^2} 2$(算术平均大于几何平均)

然后就可以快乐地打暴力了。

复杂度 $O(N+M)$ ( $M$ 为答案对数）

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define vi vector<int>
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=200010;
int dx[]={0,0,1,1,1},dy[]={0,1,-1,0,1};
int n,k;
map<pii,vi>mp;
vector<pii>ans;
struct node{
	int x,y;
}p[N];
int pf(int x){
	return x*x;
}
int dist(int i,int j){
	return pf((p[i].x-p[j].x))+pf((p[i].y-p[j].y));
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>k;
	forn(i,1,n){
		cin>>p[i].x>>p[i].y;
		mp[m_p(p[i].x/k,p[i].y/k)].pb(i);
	}
	foreach(it,mp){
		pii pr=it->fi;
		rep(i,5){
			pii m;m.fi=pr.fi+dx[i],m.se=pr.se+dy[i];
			rep(j,it->se.size()){
				rep(l,mp[m].size()){
					int id1=it->se[j],id2=mp[m][l];
					if(id1==id2)continue;
					if(id1>id2)swap(id1,id2);
					if(dist(id1,id2)<=k*k){
						ans.pb(m_p(id1,id2));
					}
				}
			}
		}
	}
	sort(ans.begin(),ans.end());
	ans.erase(unique(ans.begin(),ans.end()),ans.end());
	cout<<ans.size()<<"\n";
	rep(i,ans.size())cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
	return 0;
}

abc236h

题意

有 $n$ 个数，问有多少种序列 $a$，满足任意 $a_i\leq m$ 且 $a_i|d_i$。

$n\leq 16,m\leq 10^{18}$

做法

考虑容斥，如果就 ${\rm dp}(S)$ 表示 $S$ 中的数都相同，这么做是不对的。因为这个状态没有实际意义。

考虑容斥原理，想象一张韦恩图，然后发现若干个圆的交满足这些圆各自代表的性质。

而单独一个数是构不成任何性质的，考虑转化限制为两个数相等。

两个数相等可以理解为在他们之间连一条边。

然后同一个连通分量的数是相同的，这样就可以按边来容斥了，钦定一些边必须连，其他边随便。

${\rm ans}=\sum_{E'\in E} (-1)^{|E'|}\prod_{V'}\lfloor\dfrac m { {\rm lcm} (V')}\rfloor$

其中 $V'$ 是连通分量，$\rm lcm$ 为这个连通分量中所有的数的 $\rm lcm$。

枚举边肯定不行，考虑把一张图分成若干个连通分量，显然如果把容斥系数的 $-1$ 拆分开来给各连通分量再乘起来也是可以的。

然后这个式子就是每个连通分量的每一种可能的构成的容斥系数乘起来再相加。

根据乘法原理，把每个连通分量的每种可能的构成的容斥系数先相加再相乘。

然后一个连通分量能选的数的可能性（式子中含 $\rm lcm$ 的部分）可以先拿出来，算里面的容斥系数之和。

这样的话就是要算大小为 $n$ 的连通分量有偶数条边的情况数减去有奇数条边的情况数。

手推几个得到规律 $g(n)=(-1)^{n-1}(n-1)!$，再乘上 $\lfloor\dfrac m { {\rm lcm} (V')}\rfloor$，这样就能预处理出每个连通块的总容斥系数 $f(S)$。

这个 $g$ 的规律可以严谨证明。贺一个官方题解放在这里。

• $g(1)=1$

• 如果 $n\geq 2$，不要求图强制联通，选奇数条和偶数跳边的种类数是一样的。设 $T$ 是 $1$ 所在的连通分量。正难则反去掉 $T$ 不为全集的情况。总共的情况数显然是奇偶各一半 $=0$。如果 $T$ 之外的点至少 $2$ 个，这些点互相连边可能数奇偶各一半，直接消掉，如果只有一个，那就是 $n-1$ 种。因为已经钦定了 $T$ 是包含 $1$ 的连通分量。然后 $T$ 种 $n-1$ 个连通的容斥系数是 $g(n-1)$，所以最后 $g(n)=-(n-1)g(n-1)$ 成立。

把这些合并起来，就状压 dp，枚举子集来合并，${\rm dp}(S)$ 为 $S$ 的答案。

为了去重，用经典的套路，每次用 $f(S1)\times {\rm dp}(S2)$ 来更新 ${\rm dp}(S1\cup S2)$。

每次加入一个连通分量，钦定加入集合最小元素所在的连通分量，就可以去重。

时间复杂度：$O(3^n)$。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=20,M=(1<<16)+10,mod=998244353;
int n,m;
int a[N],cnt[M],coef[N];
int dp[M],f[M];
int lowbit(int x){
	return x&(-x);
}
int lcm(int x,int y){
	int gcd=__gcd(x,y);
	x/=__gcd(x,y);
	if(x>m/y)return m+1;
	else return x*y;
}
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	rep(i,n)cin>>a[i];
	coef[1]=1;
	forn(i,2,n)coef[i]=coef[i-1]*(mod-(i-1))%mod;
	rep(i,1<<n){
		cnt[i]=__builtin_popcount(i);
	}
	f[0]=1;
	rep(S,1<<n){
		if(!S)continue;
		f[S]=1;
		rep(i,n){
			if((S>>i)&1){
				f[S]=lcm(f[S],a[i]);
			}
		}
		f[S]=(m/f[S])%mod;f[S]=f[S]*coef[cnt[S]]%mod;
	}
	dp[0]=1;
	rep(S,1<<n){
		if(!S)continue;
		int x=lowbit(S);
		for(int S1=S;S1;S1=(S1-1)&S){
			if(S1&x){
				dp[S]+=f[S1]*dp[S^S1]%mod;
				dp[S]%=mod;
			}
		}
	}
	cout<<dp[(1<<n)-1]<<"\n";
	return 0;
}

abc237h

题意

给一个长度为 $n$ 的字符串 $s$，求最多能选多少个回文子串使得不存在其中一个是另一个的子串。

$n\leq200$

做法

暴力找出所有不同的回文子串，这个东西不超过 $n$ 个。

因为往 $s$ 后加入一个字符 $c$，最多只能新得到一个不同的回文串，如果有两个，更长的那个肯定包含更短的那个，在之前更短的已经有过了。

暴力找出来不同的回文子串。最小割模型。

拆点放到两边，中间的边容量 $\rm inf$，割不了，和 $s,t$ 之间的容量为 $1$，表示不选这个串。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=80010,M=2314514,inf=1e9;
string str;
set<string>st;
string ss[N];
int s,t;
int head[N],cur[N];
struct edge{
	int v,w;
	int cur;
	int nxt;
}e[M<<1];
int cnt=1;
void addedge(int u,int v,int w){
	cnt++;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
} 
int dep[N];
bool bfs(){
	forn(i,1,t){
		cur[i]=head[i];
		dep[i]=0;
	}
	dep[s]=1;
	queue<int>q;
	while(!q.empty())q.pop();
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int p=head[u];p;p=e[p].nxt){
			int v=e[p].v;
			if(!dep[v]&&e[p].w){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	} 
	return (dep[t]!=0);
}
int dfs(int u,int in){
	if(u==t)return in; 
	int out=0;
	for(int p=cur[u];p;p=e[p].nxt){
		cur[u]=p;
		int v=e[p].v,w=e[p].w;
		if(dep[v]!=dep[u]+1||e[p].w==0)continue;
		int res=dfs(v,min(in,w));
		in-=res;
		out+=res;
		e[p].w-=res;
		e[p^1].w+=res;
		if(!in)break;
	}
	if(out==0)dep[u]=0;
	return out;
}
int ans=0;
int maxflow(){
	while(bfs()){
		ans+=dfs(s,inf);
	}
	return ans;
}
bool chk(string s){
	rep(i,s.size()){
		int j=s.size()-1-i;
		if(j<i)break;
		if(s[i]!=s[j])return 0;
	}
	return 1;
}
string a[N];
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>str;
	rep(i,str.size()){
		forn(j,i,str.size()-1){
			string qwq=str.substr(i,j-i+1);
			if(chk(qwq))st.insert(qwq);
		}
	}
	int tot=0;
	for(auto k:st){
		a[++tot]=k;
	}
	s=tot*2+1;t=s+1;
	forn(i,1,tot){
		addedge(s,i,1);addedge(i,s,0);
		addedge(i+tot,t,1);addedge(t,i+tot,0);
	}
	forn(i,1,tot){
		forn(j,1,tot){
			if(i==j)continue;
			if(a[i].find(a[j])!=string::npos){
				addedge(i,j+tot,1);addedge(j+tot,i,0);
			}
		}
	}
	cout<<tot-maxflow()<<"\n";
	return 0;
}

abc238h

记不得了。大哭。简单写写吧。

先破环成链，然后把删人的过程倒序考虑变成加人，区间dp，状态 ${\rm dp}(l,r)$ 和 ${\rm cost}(l,r)$ 表示 $l$ 和 $r$，已经填好，再往里填别的的方案数和总贡献，然后最后再除以情况数得到期望。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=605,mod=998244353;
int n;
string s;
int dp[N][N],cost[N][N],C[N][N];
int qpow(int n,int k){
	int ans=1;
	while(k){
		if(k&1){
			ans*=n;ans%=mod;
		}
		n*=n;n%=mod;
		k>>=1;
	}
	return ans;
}
int inv(int x){
	return qpow(x,mod-2);
}
signed main(){
	ios::sync_with_stdio(0);
	forn(i,0,600)C[i][0]=1;
	forn(i,1,600)forn(j,1,i){
		C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
	cin>>n>>s;s=s+s;s=" "+s;n=n+n;
	forn(i,1,n-1)dp[i][i+1]=1;
	forn(len,3,n)forn(l,1,n){
		int r=l+len-1;if(r>n)break;
		forn(x,l,r){
			if(s[l]=='R'){
				dp[l][r]+=dp[l][x]*dp[x][r]%mod*C[r-l-2][x-l-1]%mod;
				dp[l][r]%=mod;
			}
			if(s[r]=='L'){
				dp[l][r]+=dp[l][x]*dp[x][r]%mod*C[r-l-2][x-l-1]%mod; 
				dp[l][r]%=mod;
			}
			if(s[l]=='R'){
				cost[l][r]+=dp[l][x]*dp[x][r]%mod*C[r-l-2][x-l-1]%mod*(x-l)%mod;
				cost[l][r]%=mod;
				cost[l][r]+=dp[l][x]*cost[x][r]%mod*C[r-l-2][x-l-1]%mod;
				cost[l][r]%=mod; 
				cost[l][r]+=cost[l][x]*dp[x][r]%mod*C[r-l-2][x-l-1]%mod;
				cost[l][r]%=mod;
			} 
			if(s[r]=='L'){
				cost[l][r]+=dp[l][x]*dp[x][r]%mod*C[r-l-2][x-l-1]%mod*(r-x)%mod;
				cost[l][r]%=mod; 
				cost[l][r]+=dp[l][x]*cost[x][r]%mod*C[r-l-2][x-l-1]%mod;
				cost[l][r]%=mod; 
				cost[l][r]+=cost[l][x]*dp[x][r]%mod*C[r-l-2][x-l-1]%mod;
				cost[l][r]%=mod;
			}
		}
	}
	int ans=0;
	forn(i,1,n/2){
		ans+=cost[i][i+n/2];ans%=mod;
	}
	int fm=1;
	forn(i,1,n/2){
		fm=fm*i%mod;
	}
	ans*=inv(fm);ans%=mod;
	cout<<ans<<"\n";
	return 0;
}

abc241h

题意

有 $n$ 种卡牌，第 $i$ 种写着 $A_i$，共 $B_i$ 张。

从中选 $m$ 张的价值为写的 $A$ 全部乘起来。

求所有方案的价值和，每种卡牌中不区分，即两种方案不同当且仅当存在至少一种牌选的个数不同。

$n\leq16$

$m\leq10^{18},B\leq10^{17}$

做法

重量级+1。

一眼生成函数。记 $f_i(x)$ 为第 $i$ 种牌的生成函数，$a=A_i,b=B_i$。

$f_i(x)=1+ax+a^2x^2+...+a^bx^b$

这个等比数列的封闭形式很好推。然后得到

$f_i(x)=\dfrac {1-a^{b+1}x^{b+1}} {1-ax}$

那么要求的就是

$[x^m]\dfrac {\prod\limits_{i=1}^n({1-A_i^{B_i+1}x^{B_i+1})}} {\prod\limits_{i=1}^n(1-A_ix)}$

上面有 $2^n$ 项，下面有 $n+1$ 项。

先看下面。显然可以构造出一组有理数解使得

$\dfrac 1 {(1-A_1x)(1-A_2x)...(1-A_nx)}=\dfrac {c_1} {1-A_1x}+\dfrac {c_2} {1-A_2x}+...+\dfrac {c_n} {1-A_nx}$

因为右边通分得到左边。

两边同时乘上左边的分母，得到

$1=\sum\limits_{i=1}^nc_i\prod_{j=1,j\neq i}^n (1-A_jx)$

把 $x=A_1^{-1},A_2^{-1}...$ 带入，得到若干个方程，第 $i$ 个形如

$1=c_i\prod\limits_{j=1,j\neq i}^n(1-A_jA_i^{-1})$

暴力算算，把 $c$ 都求出来。

对于原式分子部分，考虑其中一项 $dx^k$，那么下面这个式子的第 $x^{m-k}$ 的系数乘上 $d$ 就是对答案的贡献。

$\dfrac {c_1} {1-A_1x}+\dfrac {c_2} {1-A_2x}+...+\dfrac {c_n} {1-A_nx}$

每一项是一个等比数列的生成函数，快速幂做一下就好了。

时间复杂度：$O(n2^n\log m)$。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=18,M=(1<<16)+10,mod=998244353;
int qpow(int n,int k){
	int ans=1;
	while(k){
		if(k&1)ans=ans*n%mod;
		n=n*n%mod;
		k>>=1;
	}
	return ans;
}
int rev(int x){
	return qpow(x,mod-2);
}
int n,m;
int a[N],b[N];
int c[N],qwq[N];
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	rep(i,n)cin>>a[i]>>b[i];
	rep(i,n){
		int sum=1;
		rep(j,n){
			if(i==j)continue;
			sum*=(1-a[j]*rev(a[i])%mod+mod)%mod;sum%=mod;
		}
		c[i]=rev(sum);
	}
	int ans=0; 
	rep(i,n){
		qwq[i]=(mod-qpow(a[i],b[i]+1))%mod;
	}
	rep(i,1<<n){
		int d=1,k=0;
		rep(j,n){
			if((i>>j)&1){
				d*=qwq[j]%mod;d%=mod;
				k+=b[j]+1;
			}
		}
		k=m-k;
		if(k<0)continue;
		rep(j,n){
			ans+=c[j]*qpow(a[j],k)%mod*d%mod;
			ans%=mod;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

abc242h

题意

有 $n$ 个位置，$m$ 个区间。

每次会随机选出一个区间，并把区间的位置变成黑色。

问所有位置都变黑色的期望步数。

$n,m\leq400$

做法

min-max 容斥有很好的性质，对期望依然成立。

于是算位置最后变黑不如算位置最早变黑。

对子集 $T$ 进行 dp。

${\rm dp}(i,j)$ 表示前 $i$ 个位置 $i$ 必选， 能覆盖到 $T$ 中的点的线段有 $j$ 条的容斥系数总和。

转移就枚举上一次选的位置。

最后贡献进答案，$i$ 个选到 $j$ 个中的期望次数是 $\frac i j$。这个可以解方程得到。

代码是贺的三维的，他的状态 $j$ 那一维是反着来的。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=410,mod=998244353;
int qpow(int n,int k){
	int ans=1;
	while(k){
		if(k&1)ans=ans*n%mod;
		n=n*n%mod;
		k>>=1;
	}
	return ans;
}
int n,m;
int cnt[N][N];
int dp[N][N][2];
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	rep(i,m){
		int l,r;
		cin>>l>>r;
		forn(a,1,l)forn(b,r,n){
			cnt[a][b]++;
		}
	} 
	dp[0][0][0]=1;
	forn(i,0,n)rep(c,m)forn(j,i+1,n+1){
		(dp[j][c+cnt[i+1][j-1]][0]+=dp[i][c][1])%mod;
		(dp[j][c+cnt[i+1][j-1]][1]+=dp[i][c][0])%mod;
	}
	int ans=0;
	rep(i,m){
		(ans+=dp[n+1][i][0]*m%mod*qpow(m-i,mod-2)%mod)%mod;ans%=mod;
		(ans+=mod-dp[n+1][i][1]*m%mod*qpow(m-i,mod-2)%mod)%mod;ans%=mod;
	}
	cout<<ans<<"\n";
	return 0;
}

abc246h

题意

有一个长度为 $n$ 的只由 01? 组成的字符串，? 既可以是 0 也可以是 1。

$q$ 次询问每次修改一个位置后求不同子序列个数。

$n,q\leq10^5$

做法

没有修改操作就是直接 dp。然后对 $s_i$ 是什么分类讨论，写出来简单的转移式。

${\rm dp}(i,0/1)$ 表示前 $i$ 位最后为 0/1 的不同子序列个数，转移必须接上去，去重。

$s_i=0\\ {\rm dp}(i,0) = {\rm dp}(i-1,0) + ({\rm dp}(i-1,1) + 1)\\ {\rm dp}(i,1) = {\rm dp}(i-1,1) \\ s_i=1\\ {\rm dp}(i,0)={\rm dp}(i-1,0)\\ {\rm dp}(i,1)={\rm dp}(i-1,1)+({\rm dp}(i-1,0)+1)\\ s_i=?\\ {\rm dp}(i,0)={\rm dp}(i-1,0)+({\rm dp}(i-1,1)+1)\\ {\rm dp}(i,1)={\rm dp}(i-1,1)+({\rm dp}(i-1,0)+1)$

矩阵乘法能做。线段树维护，支持带修。

其实好像叫是动态 dp。

时间复杂度：$O(n\log n)$。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=100010,mod=998244353;
struct mat{
	int a[3][3];
};
mat mul(mat a,mat b){
	mat c;
	rep(i,3)rep(j,3)c.a[i][j]=0;
	rep(i,3)rep(j,3)rep(k,3){
		c.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod;
		c.a[i][j]%=mod;
	}
	return c;
}
int to(char c){
	if(c=='0')return 0;
	if(c=='1')return 1;
	return 2;
}
mat tran[3];
mat tr[N<<2];
string s;
int n,q;
void out(mat x){
	rep(i,3){
		rep(j,3){
			cout<<x.a[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<"\n";
}
void build(int id,int l,int r){
	if(l==r){
		tr[id]=tran[to(s[l])];
		return;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);build(id<<1|1,mid+1,r);
	tr[id]=mul(tr[id<<1],tr[id<<1|1]); 
} 
void upd(int id,int l,int r,int pos){
	if(l==r){
		tr[id]=tran[to(s[l])];
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid)upd(id<<1,l,mid,pos);
	else upd(id<<1|1,mid+1,r,pos);
	tr[id]=mul(tr[id<<1],tr[id<<1|1]); 
}
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	rep(i,3)rep(j,3)rep(k,3){
		tran[k].a[i][j]=0;
	}
	rep(i,3)rep(j,3)rep(k,(N<<2)){
		tr[k].a[i][j]=0;
	}
	tran[0].a[0][0]=tran[0].a[1][0]=tran[0].a[2][0]=tran[0].a[1][1]=tran[0].a[2][2]=1;
	tran[1].a[0][0]=tran[1].a[0][1]=tran[1].a[1][1]=tran[1].a[2][1]=tran[1].a[2][2]=1;
	tran[2].a[0][0]=tran[2].a[1][0]=tran[2].a[2][0]=tran[2].a[1][1]=tran[2].a[2][2]=1;
	tran[2].a[1][0]=tran[2].a[0][1]=tran[2].a[1][1]=tran[2].a[2][1]=tran[2].a[2][2]=1;
	cin>>n>>q;
	cin>>s;s=' '+s;
	build(1,1,n);
	while(q--){
		int x;char c;
		cin>>x>>c;
		s[x]=c;
		upd(1,1,n,x);
		cout<<(tr[1].a[2][0]+tr[1].a[2][1]+tr[1].a[2][2]-1+mod)%mod<<"\n";
	}
	return 0;
}

abc247h

题意

有 $n$ 个人，第 $i$ 个人颜色为 $c_i$，每次可以交换两个人，问恰好 $k$ 次操作过后每个人颜色都和原来一样的方案数。

$n\leq2\times 10^5$

做法

首先值可能交换颜色一样的人。 所以每个颜色单独做。 考虑一个排列需要的最小交换次数 $x$，这样的话当 $x\leq k$ 并且 $x,k$ 奇偶性相同时这个排列才可以被换出来。 因为 $x$ 就等于 $n$ 减去环的个数，而一次交换会改变环的奇偶性。 那就 dp 做。 ${\rm dp}(i,j)$ 表示前 $i$ 个数，有 $j$ 个环。 转移是 ${\rm dp}(i,j)={\rm dp}(i-1,j-1)+(i-1)\times {\rm dp}(i-1,j)$ 容易发现这就是一个第一类斯特林数，要求一整行。 求完之后还得对所有颜色的生成函数乘起来。得到最小交换次数为 $x$ 的有多少情况。 所以考虑 $\begin{bmatrix}n \\ i\end{bmatrix}$ 的生成函数。

$F_n(x)=\sum\limits_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix} x^i$

根据递推式推下去有

$F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x)\\ F_n(x)=\prod\limits_{i=0}^{n-1}(x+i)=\frac {(x+n-1)!} {(x-1)!}\\$

这是 $x^{\overline n}$，在读入颜色的时候按序给一个 $(x+{\rm cnt})$ 的函数。

然后把这所有的函数卷积起来。用分治的话复杂度是两个 $\log$，就能过了。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define vi vector<int>
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=600010,mod=998244353,ggg=3,invggg=(mod+1)/3;
int qpow(int n,int k){
	int ans=1;
	while(k){
		if(k&1)ans=ans*n%mod;
		n=n*n%mod;
		k>>=1;
	}
	return ans;
}
int t[N<<1];
void ntt(vi &a,int fl){
	int n=a.size();
	rep(i,n)t[i]=((t[i>>1]>>1)|((i&1)*(n>>1)));
	rep(i,n)if(i<t[i])swap(a[i],a[t[i]]);
	int o;if(fl)o=ggg;else o=invggg; 
	for(int len=2;len<=n;len<<=1){
		int gn=qpow(o,(mod-1)/len);
		for(int j=0;j<n;j+=len){
			int w=1;
			for(int k=j;k-j<(len>>1);k++){
				int cur=w*a[k+(len>>1)]%mod;
				a[k+(len>>1)]=(a[k]-cur+mod)%mod;a[k]=(a[k]+cur)%mod;
				w=w*gn%mod;			
			}
		}
	}
}
vi mul(vi f,vi g){
	int m=f.size()+g.size()-1;
	int n=1;
	while(n<m)n<<=1;
	while(f.size()<n)f.pb(0);
	while(g.size()<n)g.pb(0);
	ntt(f,1);ntt(g,1);
	rep(i,n)f[i]=f[i]*g[i]%mod;
	ntt(f,0);
	int rev=qpow(n,mod-2);
	rep(i,n)f[i]=f[i]*rev%mod;
	return f;
}
int n,k;
int cnt[N];
int a[N];
vi solve(int l,int r){
	if(l==r){
		vi qwq;
		qwq.pb(a[l]);qwq.pb(1);
		return qwq;	
	}
	int mid=l+r>>1;
	return mul(solve(l,mid),solve(mid+1,r));
}
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>k;
	forn(i,1,n){
		int x;cin>>x;
		a[i]=cnt[x];cnt[x]++;
	}
	vi res=solve(1,n);
	int ans=0;
	rep(i,res.size()){
		if(n-i<=k&&(n-i)%2==k%2){
			ans+=res[i];ans%=mod;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

abc250h

题意

$n$ 点 $m$ 边的无向图，前 $k$ 个是房子。

$q$ 次询问，问是否能从 $x$ 移动到 $y$ 任何时刻都不能距离上一次离开房子的时间 $>t$ 。

$n,m,q\leq 2\times10^5$

做法

考虑一张前 $k$ 个点的完全图，边权是最短路。

这个可以 Boruvka 直接做了。

然后发现，由于你这张图找个生成树取代了原来的图，所以你可以从原来的边入手。

通过原来的边，得到若干条边，具体地，对每条边，取 $a$ 最近的房子和 $b$ 最近的房子。

也可以理解为你走过这条边的时候都往两个最近的中转一下肯定不会更差。

所以这条路径不考虑 $a$ 和 $b$ 就是直接把这两个最近的房子连起来，把这样所有的 $O(m)$ 条边找出来跑 Kruskal。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=200010;
int n,m,k,q;
vector<pii>g[N];
int dis[N],idx[N];
bool vis[N];
struct edge{
	int u,v,w;
}e[N],E[N];
bool cmp(edge x,edge y){
	return x.w<y.w;
}
int tot=0,cnt;
priority_queue<pii,vector<pii>,greater<pii> >pq;
void Dijkstra(){
	memset(dis,0x3f,sizeof(dis));
	forn(i,1,k){
		dis[i]=0;idx[i]=i;
		pq.push(m_p(0,i));
	}
	while(!pq.empty()){
		int u=pq.top().se;pq.pop();
		if(vis[u])continue;
		vis[u]=1;
		rep(i,g[u].size()){
			int v=g[u][i].fi,w=g[u][i].se;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;idx[v]=idx[u];
				pq.push(m_p(dis[v],v));
			}
		}
	}
	forn(i,1,m){
		int x=e[i].u,y=e[i].v,w=e[i].w;
		if(idx[x]!=idx[y]){
			E[++tot]=(edge){idx[x],idx[y],dis[x]+dis[y]+w};
		}
	}
}
int fa[N<<1];
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
vector<int>G[N<<1];
int par[20][N<<1],val[N<<1],dep[N<<1];
void dfs(int u,int p){
	par[0][u]=p;dep[u]=dep[p]+1;
	rep(i,G[u].size()){
		int v=G[u][i];
		if(v==p)continue;
		dfs(v,u);
	}
}
void Kruskal(){
	cnt=k;
	forn(i,1,k)fa[i]=i;
	sort(E+1,E+tot+1,cmp);
	forn(i,1,tot){
		int x=E[i].u,y=E[i].v;
		x=find(x);y=find(y);
		if(x!=y){
			++cnt;
			fa[x]=fa[y]=cnt;
			fa[cnt]=cnt;
			val[cnt]=max(val[x],val[y]);
			val[cnt]=max(val[cnt],E[i].w);
			G[cnt].pb(x);G[cnt].pb(y);
		}
	}
	dfs(cnt,0);
	forn(i,1,18){
		forn(j,1,cnt){
			par[i][j]=par[i-1][par[i-1][j]];
		}
	}
}
int lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);//dep[x]<=dep[y]
	fore(i,18,0){
		if(dep[par[i][y]]>=dep[x])y=par[i][y];
	}
	if(x==y)return x;
	fore(i,18,0){
		if(par[i][x]!=par[i][y]){
			x=par[i][x];y=par[i][y];
		}
	}
	return par[0][x];
}
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m>>k;
	rep(i,m){
		int a,b,c;cin>>a>>b>>c;
		g[a].pb(m_p(b,c));g[b].pb(m_p(a,c));
		e[i+1]=(edge){a,b,c};
	} 
	Dijkstra();
	Kruskal();
	cin>>q;
	while(q--){
		int x,y,t;
		cin>>x>>y>>t;
		int z=lca(x,y);
		if(val[z]>t)cout<<"No\n";
		else cout<<"Yes\n";
	}
	return 0;
}

abc253h

题意

一张 $n$ 个点的图，开始没有边，每一步从输入的边集中随机一条边加进去。

对每个 $k\in [1,n-1]$，求第 $k$ 步过后为森林的概率。

$n\leq 14,m\leq 500$

做法

用 ${\rm dp}(S)$ 表示 $S$ 中的恰好构成一棵树的情况数。总情况数很好算，最后除一下就好了。

考虑两个树合并成一棵大树。如果直接枚举子集会重复。

于是我们可以钦定最后加入的点一定是最小的点 $x$。

这样 $S1$ 和 $S2$，交集为空，并集为 $S$，合并起来，假设 $x$ 在 $S2$ 中，向 $S1$ 中连边转移。

然后枚举子集转移还是会重复，重复的情况很简单，就是 $x$ 只有两条边，沟通了两个集合。

所以可以转移的时候规定一下顺序，比如只有 $S1>S2$ 才转移。

第 $k$ 步过后的森林边数固定，所以树的个数也固定，就考虑再 dp 把树合并起来。

$f(i,S)$ 为 $S$ 中的点有 $i$ 棵树，转移类似经典区间dp的去重思路，一个 $f$ 和一个 $\rm dp$ 乘起来，规定好顺序。

最后一个情况还有系数是加边的顺序，除以总情况数，贡献到答案里面去。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=16,M=505,S=(1<<14)+10,mod=998244353;
int qpow(int n,int k){
	int ans=1;
	while(k){
		if(k&1)ans=ans*n%mod;
		n=n*n%mod;
		k>>=1;
	}
	return ans;
}
int n,m;
int num[N][N],cnt[N][S];
int bin[S];
int lowbit(int x){
	return x&(-x);
}
int dp[S],f[N][S];
int fac[N];
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	rep(i,n)bin[1<<i]=i;
	rep(i,m){
		int x,y;cin>>x>>y;x--;y--;
		num[x][y]++;num[y][x]++;	
	}
	rep(s,1<<n){
		rep(i,n){
			if((s>>i)&1)continue;
			rep(j,n){
				if(!((s>>j)&1))continue;
				cnt[i][s]+=num[i][j];
			}
		}
	}
	dp[0]=1; 
	rep(i,n)dp[1<<i]=1;
	rep(s,1<<n){
		if(__builtin_popcount(s)<=1)continue;
		int x=lowbit(s);int y=bin[x];
		int msk=s^x;
		for(int s1=msk;s1;s1=(s1-1)&msk){
			int s2=msk^s1;
			if(s1>s2){
				s2|=x;
				dp[s]+=dp[s1]*dp[s2]%mod*cnt[y][s1]%mod;
				dp[s]%=mod;
			}
		}
	}
	f[0][0]=1;
	forn(i,1,n-1){
		rep(s,1<<n){
			for(int s1=s;s1;s1=(s1-1)&s){
				int s2=s^s1;
				if(s1>s2){
					f[i][s]+=f[i-1][s2]*dp[s1]%mod;
					f[i][s]%=mod; 
				}
			}
		}
	}
	fac[0]=1;
	forn(i,1,n)fac[i]=fac[i-1]*i%mod;
	forn(i,1,n-1){
		int ans=f[n-i][(1<<n)-1];
		ans*=fac[i];ans%=mod;
		int rev=qpow(m,i);rev=qpow(rev,mod-2);
		ans*=rev;ans%=mod;
		cout<<ans<<"\n";
	}
	return 0;
}

abc255h

题意

有 $n$ 棵树，第 $i$ 棵树每秒会结出 $i$ 个果子。

有 $q$ 个操作，每次操作给定 $l,r,d$，在第 $d$ 天收割 $[l,r]$ 之间的果子。

每次操作需要输出收割的果子数量。收割完后那棵树归 $0$，但还会接着长。

$n,l,r,d\leq10^{18}$

$q\leq 2\times10^5$

做法

貌似是第一次现场过Ex。最简单的Ex。

介绍两个做法。

第一个做法，对于每个树维护上一次被收割的时间，然后区间查询时 $i$ 的贡献为 $i\times(d-t_i)$。其中 $t_i$ 是 $i$ 上一次被收割的时间。

然后区间修改 $t_i$。

这个区间修改区间查询用动态开点线段树就很好维护，或者离散化+分块也行。

第二个做法是我赛时写的，是大名鼎鼎的珂朵莉树。

如果不会珂朵莉树可以学一下。

link

一点有用的复杂度分析

众所周知，当珂朵莉树只有 assign 操作的时候，复杂度非常的对。

因为每次操作得到两个新的分界点，填补上区间内所有分界点。

于是每个分界点最多会在后面被填上一次。一个分界点会使得查询的时候多遍历一个区间，也就是多遍历的区间数是 $O(q)$ 级别的。

再加上 set 自己的复杂度就是 $O(q\log n)$。

代码超级好写。

#include<bits/stdc++.h>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define m_p make_pair
#define pb push_back
#define fi first
#define se second
#define int ll
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
const int N=200010,mod=998244353;
int qpow(int n,int k){
	int ans=1;
	while(k){
		if(k&1){
			ans=ans*n%mod;
		}
		n=n*n%mod;
		k>>=1;
	}
	return ans;
}
int inv2;
int n,q;
struct node{
	int l,r;
	mutable int v;
	node(int l,int r=0,int v=0):l(l),r(r),v(v){}
	bool operator<(const node &x)const{
		return l<x.l;
	}
};
set<node>s;
set<node>::iterator split(int pos){
    set<node>::iterator it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos)return it;it--;
    if(it->r<pos)return s.end();
    int l=it->l,r=it->r,v=it->v;
    s.erase(it);s.insert(node(l,pos-1,v));
    return s.insert(node(pos,r,v)).fi;
}
int assign(int l,int r,int x){
	set<node>::iterator itr=split(r+1),itl=split(l);
	int ans=0;
	for(set<node>::iterator it=itl;it!=itr;it++){
		int L=it->l,R=it->r,d=it->v;
		L%=mod;R%=mod;
		int s=(L+R)%mod*(R-L+1+mod)%mod*inv2%mod;
		ans+=s*(x-d+mod)%mod;ans%=mod;
	}
	s.erase(itl,itr);s.insert(node(l,r,x));
	return ans;
}
signed main(){
    cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	inv2=qpow(2,mod-2);
	cin>>n>>q;
	s.insert(node(1,n,0));
	while(q--){
		int d,l,r;
		cin>>d>>l>>r;d%=mod;
		cout<<assign(l,r,d)<<"\n";
	}
	return 0;
}