欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

2020.4.29省选模拟赛 A B C（容斥、图论计数DP、树套树+set）

程序员文章站 2023-12-24 22:55:09
...

A

题目描述

或许前路永夜，即便如此我也要前进，因为星光即使微弱也会为我照亮前途。

已知一个 n*m 的矩阵,矩阵的每个元素都是非负整数.

已知第 i 行的最大值为 ri ,第 j 列的最大值为 cj .求矩阵数目.

输入格式

第一行一个数 T ,表示数据组数.

对于每组测试数据,第一行两个数 n , m 表示矩阵大小.

接下来一行 n 个数,表示 r 数组 接下来一行 m 个数,表示 c 数组

输出格式 对于每组测试数据,输出一行一个数,表示符合要求的矩阵的数目模 1e9+7

样例见下发文件

数据范围

• 对于 30% 的数据，输入的最大数不超过4;

• 对于 50% 的数据，n , m <= 100.

• 对于 100% 的数据，n , m <= 1000 , T <= 20 .

 

 

题解

简单容斥

首先r、c数组的内部顺序对答案没有关系，所以先把r、c数组都从小往大排序

从小往大枚举权值c，每次把最大值严格等于c的行列提取出来算答案

具体怎么计算答案呢，如图
2020.4.29省选模拟赛 A B C（容斥、图论计数DP、树套树+set）

如果我们当前枚举的c是1

那么这一片红色区域的最大值都不能超过1

且每一行每一列都要存在恰好等于最大值的数

我们可以把这些行列看成限制条件进行容斥，累加的时候乘一个组合系数即可

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1005
const int mod=1000000007;
int a[N],b[N],c[2*N],cnt,n,m;
int pw1[N*N],pw2[N*N];
int ksm(int x,int y)
{
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		y>>=1;x=1ll*x*x%mod;
	}
	return ret;
}
inline int rc(int x){return x&1?-1:1;}
int C[N][N];
int main()
{
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	int T,i,j,k,p,q,x,y,mxa,mxb,ans;
	C[0][0]=1;
	for(i=1;i<=1000;i++){
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	scanf("%d",&T);
	while(T--){
		mxa=mxb=0;ans=1;
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++){scanf("%d",&a[i]);c[++cnt]=a[i];mxa=max(mxa,a[i]);}
		sort(a+1,a+n+1);
		for(i=1;i<=m;i++){scanf("%d",&b[i]);c[++cnt]=b[i];mxb=max(mxb,b[i]);}
		sort(b+1,b+m+1);
		sort(c+1,c+cnt+1);
		cnt=unique(c+1,c+cnt+1)-c-1;
		for(i=1,p=0,q=0;i<=cnt;i++){
			j=p+1;k=q+1;
			while(a[j]==c[i]&&j<=n)j++;j--;
			while(b[k]==c[i]&&k<=m)k++;k--;
			int cx=j-p,cy=k-q,lenx=n-p,leny=m-q;
			int all=lenx*cy+leny*cx-cx*cy;
			int ret=0;
			pw1[0]=pw2[0]=1;
			for(x=1;x<=all;x++){
				pw1[x]=1ll*pw1[x-1]*c[i]%mod;
				pw2[x]=1ll*pw2[x-1]*(c[i]+1)%mod;
			}
			for(x=0;x<=cx;x++)
				for(y=0;y<=cy;y++){
					int now=lenx*y+leny*x-x*y;
					ret=(1ll*ret+1ll*rc(x+y)*pw1[now]*pw2[all-now]%mod*C[cx][x]%mod*C[cy][y])%mod;
				}
			ret=(ret+mod)%mod;
			ans=1ll*ans*ret%mod;
			p=j;q=k;
		}
		printf("%d\n",ans);
	}
}

 

 

B

题目描述

星星只有在夜里才璀璨夺目啊

送你一个 n 个点 m 条边的 DAG 和参数 k ，定义一条经过 l 条边的路径的权值为 l^k. 对于 i = 1...n，求出所有 1 到 i 的路径的权值之和，对 998244353 取模.

输入格式

第一行三个整数 n，m，k，分别表示 DAG 的点数，边数和参数.

接下来 m 行，每行两个整数 ui，vi，分别表示一条从 ui 到 vi 的有向边.

输出格式

共输出 n 行，第 i 行一个整数，表示 i 号点的答案.

样例见下发文件

数据范围

• 对于 20% 的数据，n <= 2000, m <= 5000;

• 对于 另 10% 的数据， k = 1.

• 对于 另 20% 的数据， k <= 30.

• 对于 100% 的数据，1 <= n <= 100000, 1 <= m <= 200000, 0 <= k <= 500,保证从 1 出发 可以到达每个点，可能会有重边.

 

题解

不难做出暴力DP,O(nk^2)，把每个点的0~k的次方的答案都记录下来，利用组合数来进行转移

我们理性分析一下

2020.4.29省选模拟赛 A B C（容斥、图论计数DP、树套树+set）（s是第二类斯特林数）

我们可以只DP出后面的C(n,j)，最后用这个式子来算即可

复杂度O(nk)

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int gi()
{
	char c;int num=0;
	while((c=getchar())<'0'||c>'9');
	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
	return num;
}
#define N 100005
const int mod=998244353;
int fir[N],nxt[2*N],to[2*N],cnt,d[N];
void adde(int a,int b){to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;d[b]++;}
int q[N],he,ta;
int f[N][505],s[505][505],fac[505],ans[N];
inline void add(int &x, int y) { x += y; x >= mod ? x-=mod:0; }
inline int pls(int x, int y) { return x+y>=mod?x+y-mod:x+y;	}
int main()
{
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	int n,m,i,j,k,u,v,p;
	n=gi();m=gi();k=gi();
	s[0][0]=1;fac[0]=1;
	for(i=1;i<=k;i++){
		fac[i]=1ll*fac[i-1]*i%mod;
		s[i][0]=0;s[i][i]=1;
		for(j=1;j<i;j++)
			s[i][j]=(1ll*s[i-1][j-1]+1ll*s[i-1][j]*j)%mod;
	}
	for(i=1;i<=m;i++){u=gi();v=gi();adde(u,v);}
	f[1][0]=1;
	q[++ta]=1;he=1;
	while(he<=ta){
		u=q[he++];
		for(p=fir[u];p;p=nxt[p]){
			v=to[p];
			f[v][0]=(1ll*f[v][0]+1ll*f[u][0])%mod;
			for(i=1;i<=k;i++)
				f[v][i]=(1ll*f[v][i]+1ll*f[u][i]+1ll*f[u][i-1])%mod;
			if(!--d[v])q[++ta]=v;
		}
	}
	for(i=1;i<=n;i++){
		int ret=0;
		for(j=0;j<=k;j++)
			ret=(1ll*ret+1ll*s[k][j]*fac[j]%mod*f[i][j])%mod;
		printf("%d\n",ret);
	}
}

 

 

C

题目描述

春天，马上就要来了

让我与你相遇的春天，就要来了

再也没有你的春天，就要来了

送你一棵 n 个点的树, 树根为 1.

一开始每个点上有一个 1...n 的颜色 ci, 不同点颜色可以相同.

现在有 q 次操作, 分为两种类型:

• 1 u l r: 询问子树 u 中有多少种在 l 到 r 之间的颜色至少出现了一次

• 2 u c: 将 u 的颜色修改为 c 部分测试点

要求强制在线.

输入格式

第一行三个整数 n, q, t, 分别表示树的点数, 操作的个数和是否强制在线.

t = 0 表示不强制在线, t = 1 表示强制在线.

接下来一行 n 个整数 ci, 表示每个点的初始颜色.

接下来 n − 1 行, 每行两个整数 ui, vi, 表示一条 ui 到 vi 的边.

接下来 q 行, 每行四个或三个整数, 表示一个操作.

当 t = 1 时, 需要对第一个数以外的其他数异或 上一次询问的答案 lastans, 初始时 lastans = 0.

输出格式

对于每个询问输出一行一个整数, 表示答案.

样例见下发文件

数据范围

• 对于前 20% 的数据, n, q ≤ 5000;

• 对于前 40% 的数据, n, q ≤ 50000;

• 对于另 20% 的数据, 没有修改操作;

• 对于另 20% 的数据, t = 0;

• 对于 100% 的数据, 1 ≤ n, q ≤ 100000.

 

题解

•维护颜色相同的点的set，相邻的点在lca处-1
•区间求和用树套树

 

std题解言简意赅

٩(๑>◡<๑)۶人生第一次写树状数组套线段树，其实蛮好写的٩(๑>◡<๑)۶

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
inline int gi()
{
	char c;int num=0,flg=1;
	while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;
	while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
	return num*flg;
}
#define N 100005
int n,m,col[N],pre[N];
int fir[N],to[2*N],nxt[2*N],cnt;
void adde(int a,int b)
{
	to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;
	to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;
}
int fa[N],son[N],siz[N],dep[N],top[N];
int dfn[N],num[N],dc;
void dfs1(int u)
{
	dep[u]=dep[fa[u]]+1;siz[u]=1;
	for(int v,p=fir[u];p;p=nxt[p])if((v=to[p])!=fa[u]){
		fa[v]=u;dfs1(v);siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])son[u]=v;
	}
}
void dfs2(int u)
{
	dfn[u]=++dc;num[dc]=u;
	if(son[u]) top[son[u]]=top[u],dfs2(son[u]);
	for(int v,p=fir[u];p;p=nxt[p])
		if((v=to[p])!=fa[u]&&v!=son[u])
			top[v]=v,dfs2(v);
}
int LCA(int x,int y)
{
	while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=fa[top[x]];}
	return dep[x]<dep[y]?x:y;
}
int T[N],tot;
struct node{
	int l,r,x;
}a[N<<8];
void insert(int &i,int l,int r,int x,int k)
{
	if(!i)i=++tot;a[i].x+=k;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)insert(a[i].l,l,mid,x,k);
	else insert(a[i].r,mid+1,r,x,k);
}
int query(int i,int l,int r,int ql,int qr)
{
	if(!i||l>qr||ql>r)return 0;
	if(ql<=l&&r<=qr)return a[i].x;
	int mid=(l+r)>>1;
	return query(a[i].l,l,mid,ql,qr)+query(a[i].r,mid+1,r,ql,qr);
}
set<int> S[N];
set<int>::iterator it1,it2;
void update(int i,int x,int k){while(i<=n){insert(T[i],1,n,x,k);i+=(i&-i);}}
int getsum(int i,int l,int r){int ret=0;while(i){ret+=query(T[i],1,n,l,r);i-=(i&-i);}return ret;}
void modify(int u,int k)
{
	int c=col[u];
	update(dfn[u],c,k);
	it1=it2=S[c].find(dfn[u]);
	int l=(it1==S[c].begin()?0:*(--it1));
	int r=(++it2==S[c].end()?n+1:(*it2));
	if(l) update(dfn[LCA(num[l],u)],c,-k);
	if(r<=n) update(dfn[LCA(num[r],u)],c,-k);
	if(l&&r<=n) update(dfn[LCA(num[l],num[r])],c,k);
}
int main()
{
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
	int tp,op,i,u,v,c,l,r,ans=0;
	n=gi();m=gi();tp=gi();
	for(i=1;i<=n;i++)col[i]=gi();
	for(i=1;i<n;i++){u=gi();v=gi();adde(u,v);}
	dfs1(1);dfs2(1);
	for(i=1;i<=n;i++)S[col[i]].insert(dfn[i]);
	for(i=1;i<=n;i++){// follow the order of dfs
		c=col[num[i]];update(i,c,1);
		if(pre[c])update(dfn[LCA(num[pre[c]],num[i])],c,-1);
		pre[c]=i;
	}
	while(m--){
		op=gi();
		if(op==1){
			u=gi();l=gi();r=gi();
			if(tp)u^=ans,l^=ans,r^=ans;
			ans=getsum(dfn[u]+siz[u]-1,l,r)-getsum(dfn[u]-1,l,r);
			printf("%d\n",ans);
		}
		else{
			u=gi();v=gi();
			if(tp)u^=ans,v^=ans;
			modify(u,-1);
			S[col[u]].erase(dfn[u]);
			S[col[u]=v].insert(dfn[u]);
			modify(u,1);
		}
	}
}

 

 

 

 

 

 

 

相关标签： 图论 数据结构 数学 c++ 算法 动态规划

上一篇：

下一篇：

推荐阅读