NOIP模拟赛 11.06 by RSJ and LZY

, , , , , ,

前言

今天挂的分算少的了，才 $28$，但是 T4 数组开小少了 $8$ 分值得警戒。

还是要稳啊。

T1

Description

https://www.luogu.com.cn/problem/AT_arc060_c

Solution

倍增，签到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,a[maxn],k,q;
int fa[maxn][21];
signed main(void){
	int i,x,y,j;
	read(n);
	for (i=1;i<=n;i++) read(a[i]);
	read(k);read(q);
	int now=1;
	for (i=1;i<=n;i++) {
		while (now<n&&a[now+1]-a[i]<=k) now++;
		fa[i][0]=now;
	}
	for (j=1;j<=20;j++)	
		for (i=1;i<=n;i++) 
			fa[i][j]=fa[fa[i][j-1]][j-1];
	while (q--) {
		int ans=0;
		read(x),read(y);
		if (x>y) swap(x,y);
		for (i=20;i>=0;i--) if (fa[x][i]<y) x=fa[x][i],ans+=(1<<i);
		if (x&&fa[x][0]>=y) ans++;
		else ans=-1;
		printf("%d\n",ans);
	}
	return 0;
}

T2

Description

DMOPC ‘22 Contest 2 P4 https://dmoj.ca/problem/dmopc22c2p4

Solution

先处理最小值，然后把最小值相等的部分加起来。

观察到可以不删的那一部分就是选定一个根，根到每种颜色的子树之上的部分。

组合数预处理出来，方案数先换根算一算子树内的和不包含子树的两种。

考虑换根解决每个颜色。

也可以暴力，用树上启发式合并。我用的是后一种，不用脑子，也不会慢很多。复杂度 $O(n\log n)$。

但是记得特判 $k=1$，如果直接加起来会算重寄掉。特殊处理一下就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 500005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,k;
vector<int>to[maxn];
int c[maxn],f[maxn],g[maxn];
int suf[maxn],isuf[maxn],siz[maxn];
int Ans[maxn],nums[maxn],son[maxn];
void add(int &x,int y) {x=(x+y)%mod;}
int C(int x,int y) {return suf[x]*isuf[y]%mod*isuf[x-y]%mod;}
int iC(int x,int y) {return isuf[x]*suf[y]%mod*suf[x-y]%mod;}
void dfs(int x,int pre) {
	siz[x]=1;f[x]=1;
	for (auto y:to[x]) if (y^pre) {
		dfs(y,x);
		f[x]=f[x]*f[y]%mod*C(siz[x]+siz[y]-1,siz[y])%mod;
		siz[x]+=siz[y];
		if (!son[x]||siz[son[x]]<siz[y]) son[x]=y;
	}
}
void dfs2(int x,int pre) {
	for (auto y:to[x]) if (y^pre) {
		int tmp=f[x]*power(f[y]*C(siz[x]-1,siz[y])%mod)%mod;
		g[y]=g[x]*tmp%mod*C(n-siz[y]-1,n-siz[x])%mod;
//		gdb(y,x,g[x],f[x],tmp,g[y]);
		dfs2(y,x);
	}
}
int vis[maxn];
vector<int>t[maxn];
void update(int x,int pre) {
	int flag=0;
	if (!vis[c[x]]) flag=1,vis[c[x]]=1,t[c[x]].push_back(x);
	for (auto y:to[x]) if (y^pre) update(y,x);
	if (flag) vis[c[x]]=0;
} 
void clear(int x,int pre) {
	t[c[x]].clear();
	for (auto y:to[x]) if (y^pre) clear(y,x);
} 
void solve(int x,int pre) {
	for (auto y:to[x]) if (y!=pre&&y!=son[x]) solve(y,x),clear(y,x);
	if (son[x]) solve(son[x],x);
	for (auto y:to[x]) if (y!=pre&&y!=son[x]) update(y,x);
	
	t[c[x]].clear();t[c[x]].push_back(x);
	int cnt=0,tot=1,i=c[pre];
	for (auto y:t[i]) cnt+=siz[y],tot=tot*f[y]%mod*C(cnt,siz[y])%mod;//,gdb(x,y,siz[y]);
	cnt+=n-siz[x];tot=tot*g[x]%mod*C(cnt,n-siz[x])%mod;
//	gdb(x,pre,c[pre],i,cnt,tot);
	if (Ans[i]>cnt) Ans[i]=cnt,nums[i]=tot;
	else if (Ans[i]==cnt&&cnt!=n) Ans[i]=cnt,add(nums[i],tot);
}
void calc(void) {
	int i;
	nums[1]=0;
	for (i=1;i<=n;i++) add(nums[1],f[i]*g[i]%mod*C(n-1,n-siz[i])%mod);//,gdb(i,f[i],g[i]);
	printf("%lld\n",nums[1]);
}
signed main(void){
	int i,x,y;
	read(n);read(k);
	for (i=1;i<=n;i++) read(c[i]),nums[i]=1,Ans[i]=1e9;
	for (i=1;i<n;i++) {
		read(x),read(y);
		to[x].push_back(y);
		to[y].push_back(x);
	}
	for (suf[0]=1,i=1;i<=n;i++) suf[i]=suf[i-1]*i%mod;
	for (isuf[n]=power(suf[n]),i=n;i>=1;i--) isuf[i-1]=isuf[i]*i%mod;
	dfs(1,0);
	g[1]=1;
	dfs2(1,0);
	if (k==1) return calc(),0;
	solve(1,0);
//	for (i=1;i<=n;i++) gdb(i,f[i],g[i]);
	for (i=1;i<=k;i++) if (i!=c[1]) {
		int cnt=0,tot=1;
		for (auto y:t[i]) cnt+=siz[y],tot=tot*f[y]%mod*C(cnt,siz[y])%mod;
//		gdb(cnt,tot);
		if (Ans[i]>cnt) Ans[i]=cnt,nums[i]=tot;
		else if (Ans[i]==cnt&&cnt!=n) Ans[i]=cnt,add(nums[i],tot);
	} 
//	for (i=1;i<=k;i++) gdb(i,nums[i],Ans[i]);
	for (i=1;i<=k;i++) printf("%lld\n",nums[i]);
	return 0;
}

T3

Description

AGC008 E https://www.luogu.com.cn/problem/AT_agc008_e

Solution

很有意思，也很没有意思，细节好多。

直接贺了。

https://blog.csdn.net/litble/article/details/83118814

主要的套路就是根据通常的 $(i,p_i)$ 连边与 $(i,a_i)$ 连边对应，从右边根据不同情况讨论反推左边，实际可以打表找规律或者手玩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 1000008
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int a[maxn],in[maxn],vis[maxn],cir[maxn],n;
int sum[maxn],f[maxn],ans=1,fr[maxn];
void add(int &x,int y) {x=(x+y)%mod;}
void calc(int i) {
	int x=i,now=0;
	int tmp=0,las=0,tr,lr;
	while (cir[x]) {
		cir[x]=0,++now;
		if (fr[x]) {
			if (!tmp) tmp=las=now,tr=fr[x];
			else {
				int res=(fr[x]<now-las)+(fr[x]<=now-las);
				ans=ans*res%mod;
				las=now;
			}
		}
		x=a[x];
	}
//	gdb(i,now,tmp);
	if (!tmp) sum[now]++;
	else {
		int res=(tr<now-las+tmp)+(tr<=now-las+tmp);
		ans=ans*res%mod;
	}
}
signed main(void){
	int i,j;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),in[a[i]]++;
	for (i=1;i<=n;i++) if (!vis[i]) {
		int x=i;
		while (!vis[x]) vis[x]=i,x=a[x];
		if (vis[x]!=i) continue;
		while (!cir[x]) cir[x]=1,x=a[x];
	}
	for (i=1;i<=n;i++) 
		if ((cir[i]&&in[i]>2)||(cir[i]==0&&in[i]>1)) return puts("0"),0;
	
	for (i=1;i<=n;i++) if (!in[i]) {
		int x=i,len=0;
		while (!cir[x]) len++,x=a[x];
		fr[x]=len;
	}
	for (i=1;i<=n;i++) if (cir[i]) calc(i);
	for (i=1;i<=n;i++) if (sum[i]) {
		f[0]=1;
		for (j=1;j<=sum[i];j++) {
			if (i>1&&i%2) f[j]=f[j-1]*2%mod;
			else f[j]=f[j-1];
			if (j>1) f[j]=(f[j]+(j-1)*f[j-2]%mod*i%mod)%mod;
		}
		ans=ans*f[sum[i]]%mod;
	}
	printf("%lld",ans);
	return 0;
}

T4

Description

loj6878 https://loj.ac/p/6878

Solution

太困难了，部分分写的是 FWT 的异或卷积才拿了 $32$ 分。

正解有空补。