Znzryb's Blog
0%

2025牛客WC2-M-那是我们的影子

Posted on Edited on

思路讲解

这句话可以好好琢磨一下

image

具体来说就是这样

我先根据题解的这句话写一写

AC代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75129359

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,mod=static_cast<ll>(1e9)+7;
ll N,T;
char maze[5][MAXN];
set<char> col[5];
ll factorial[15];
inline ll C(ll k,ll n) {
	// factorial[n]/factorial[n-k] 是排列数，组合数不要排列，所以再除factorial[k]
	ll res=factorial[n]%mod/((factorial[k]%mod)*(factorial[n-k]%mod));
	return res%mod;
}
void solve(){
	cin>>N;
	for(int i=0;i<5;++i) {
		col[i].clear();
	}
	vector<ll> vis(11,-1);
	vector<ll> cnt(4,0);
	set<ll> remele;
	for(int i=1;i<=9;++i) {
		remele.insert(i);
	}
	for(int i=1;i<=3;++i) {
		for(int j=1;j<=N;++j) {
			cin>>maze[i][j];
			col[j%3].insert(maze[i][j]);
		}
	}
	for(int i=1;i<=N;++i) {	// 排除一列中有多个重复元素的情况
		if(maze[1][i]==maze[2][i] && maze[1][i]!='?') {cout<<0<<'\n';return;}
		if(maze[1][i]==maze[3][i] && maze[1][i]!='?') {cout<<0<<'\n';return;}
		if(maze[2][i]==maze[3][i] && maze[2][i]!='?') {cout<<0<<'\n';return;}
	}
	for(int i=0;i<3;++i) {
		if(col[i].size()>=5) {cout<<"0\n";return;}
		if(col[i].size()==4 && col[i].find('?')==col[i].end()) {cout<<"0\n";return;}	// 没找到问号且包含四个元素也是无解的
		for(auto j:col[i]) {
			if(j=='?') continue;
			if(vis[j-'0']!=-1) { // 该元素已经被其他列占有
				cout<<0<<'\n';
				return;
			}
			vis[j-'0']=i;	// 该元素被该列占有
			cnt[i]+=1;	// 该列所拥有元素+1
			remele.erase(j-'0');
		}
	}
	// 列元素分配方案*问号分配方案=答案
	ll qm=1;
	// 计算问号分配方案
	for(int j=1;j<=N;++j) {
		ll qmcnt=0;	// 统计问号数量(question mark)
		for(int i=1;i<=3;++i) {
			if(maze[i][j]=='?') qmcnt+=1;
		}
		if(qmcnt==0) continue;
		if(qmcnt==2||qmcnt==1) qm=(qmcnt*qm)%mod;
		else qm=(6*qm)%mod;
	}
	qm=qm%mod;
	// 计算元素分配方案
	ll ele=1;
	ll rem=remele.size();
	for(int i=0;i<3;++i) {
		if(cnt[i]==3) continue;
		ele*=C(3-cnt[i],rem);
		rem-=3-cnt[i];
	}
	cout<<((ele%mod)*(qm%mod))%mod<<'\n';
	// cout<<"debug\n";
	// cout<<ele<<' '<<qm<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	factorial[0]=1;
	for(int i=1;i<=14;++i) {
		factorial[i]=(factorial[i-1]*i)%mod;
	}
	while (T--) {
		solve();
	}
	return 0;
}
/*

1
3
723
18?
?9?

1
3
13?
1??
2??

*/

心路历程（WA，TLE，MLE……）

1
2
3
4
5
6
1
3
13?
1??
2??

以下程序没有处理一列中有多个重复元素的情况

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,mod=static_cast<ll>(1e9)+7;
ll N,T;
char maze[5][MAXN];
set<char> col[5];
ll factorial[15];
inline ll C(ll k,ll n) {
	// factorial[n]/factorial[n-k] 是排列数，组合数不要排列，所以再除factorial[k]
	ll res=factorial[n]%mod/((factorial[k]%mod)*(factorial[n-k]%mod));
	return res%mod;
}
void solve(){
	cin>>N;
	for(int i=0;i<5;++i) {
		col[i].clear();
	}
	vector<ll> vis(11,-1);
	vector<ll> cnt(4,0);
	set<ll> remele;
	for(int i=1;i<=9;++i) {
		remele.insert(i);
	}
	for(int i=1;i<=3;++i) {
		for(int j=1;j<=N;++j) {
			cin>>maze[i][j];
			col[j%3].insert(maze[i][j]);
		}
	}
	for(int i=0;i<3;++i) {
		if(col[i].size()>=5) {cout<<"0\n";return;}
		if(col[i].size()==4 && col[i].find('?')==col[i].end()) {cout<<"0\n";return;}	// 没找到问号且包含四个元素也是无解的
		for(auto j:col[i]) {
			if(j=='?') continue;
			if(vis[j-'0']!=-1) { // 该元素已经被其他列占有
				cout<<0<<'\n';
				return;
			}
			vis[j-'0']=i;	// 该元素被该列占有
			cnt[i]+=1;	// 该列所拥有元素+1
			remele.erase(j-'0');
		}
	}
	// 列元素分配方案*问号分配方案=答案
	ll qm=1;
	// 计算问号分配方案
	for(int j=1;j<=N;++j) {
		ll qmcnt=0;	// 统计问号数量(question mark)
		for(int i=1;i<=3;++i) {
			if(maze[i][j]=='?') qmcnt+=1;
		}
		if(qmcnt==0) continue;
		if(qmcnt==2||qmcnt==1) qm=(qmcnt*qm)%mod;
		else qm=(6*qm)%mod;
	}
	qm=qm%mod;
	// 计算元素分配方案
	ll ele=1;
	ll rem=remele.size();
	for(int i=0;i<3;++i) {
		if(cnt[i]==3) continue;
		ele*=C(3-cnt[i],rem);
		rem-=3-cnt[i];
	}
	cout<<((ele%mod)*(qm%mod))%mod<<'\n';
	// cout<<"debug\n";
	// cout<<ele<<' '<<qm<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	factorial[0]=1;
	for(int i=1;i<=14;++i) {
		factorial[i]=(factorial[i-1]*i)%mod;
	}
	while (T--) {
		solve();
	}
	return 0;
}
/*

1
3
723
18?
?9?

1
3
13?
1??
2??

*/