E题
C. The Intriguing Obsession—cf链接
思路：
要明白这道题，首先要理解题目中的约束条件。
- 相同颜色的点之间不能直接连接
- 思考一个点的链接情况：a->b->c->a，这样才能使得两个颜色相同的点链接在一起
要明白条件首先要研究两个条件都刻画了什么特征
一个点可以不连接，可以只连接任意颜色的点，若连两个点必须连接两个颜色不同的点
转化一下就是：
一个节点至多连接两个颜色相异的点
可以看出两种颜色之间的连线的种数是
相互独立的
然后可以进一步简化问题，变成求
2
2
2
种颜色连线种数相乘！
dp做法
有详细的dp状态分析
组合数学做法
对于两种颜色，要保证相同数量的点进行连接，相同数量的点进行匹配，应该固定一种颜色的点的顺序，然后对另外一个颜色的点进行全排列
用公式概括也就是：
∑
i
=
0
m
i
n
(
a
,
b
)
C
a
i
∗
C
b
i
∗
i
!
\sum_{i=0}^{min(a,b)}C_a^i*C_b^i*i!
∑
i
=
0
m
i
n
(
a
,
b
)
C
a
i
∗
C
b
i
∗
i
!
code：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 998244353;
ll n, m, t;
ll fac[maxn];
ll q_pow(ll a, ll n, ll ans = 1){
while(n){
if(n & 1) ans=ans*a%mod;a=a*a%mod;n>>=1;
}return ans;
}
ll C(ll n, ll m)
{
ll x = 1, y = 1;
for(ll i = 1; i <= m; ++i)
x = x * i % mod, y = y * (n - i + 1) % mod;
return y * q_pow(x, mod - 2) % mod;
}
ll solve(ll a, ll b)
{
ll ans = 0;
for(int i = 0; i <= min(a, b); ++i)
ans = (ans + C(a, i) * fac[i] % mod * C(b, i) % mod) % mod;
return ans;
}
void work()
{
fac[0] = 1;
for(int i = 1; i <= maxn - 9; ++i)
fac[i] = fac[i-1] * i % mod;
cin >> n >> m >> t;
cout << solve(n, m) * solve(m, t) % mod * solve(n, t) % mod;
}
int main()
{
ios::sync_with_stdio(0);
// int TT;cin>>TT;while(TT--)
work();
return 0;
}
F题
C. Beautiful Numbers—-cf链接
思路：
给定三个数
a
,
b
,
n
（
1
<
=
a
,
b
<
=
9
)
a,b,n（1<=a,b<=9)
a
,
b
,
n
（
1
<
=
a
,
b
<
=
9
)
，如果一个数仅有
a
,
b
a,b
a
,
b
两个数组成，那么它是一个
g
o
o
d
good
g
o
o
d
数，如果
g
o
o
d
good
g
o
o
d
数的各位和也仅由
a
,
b
a,b
a
,
b
组成，那么它是
e
x
c
e
l
l
e
n
t
excellent
e
x
c
e
l
l
e
n
t
思路：
O
(
n
)
O(n)
O
(
n
)
枚举选择数字
a
a
a
的个数
i
i
i
，那么
b
b
b
就是
n
−
i
n-i
n
−
i
个，然后
c
h
e
c
k
check
c
h
e
c
k
数字
a
∗
i
+
b
∗
(
n
−
i
)
a*i+b*(n-i)
a
∗
i
+
b
∗
(
n
−
i
)
是不是全由数字
a
,
b
a,b
a
,
b
组成的，如果是，答案加上
C
n
i
C_n^i
C
n
i
，扫一遍即可
逆元和阶乘预处理，即可
O
(
1
)
O(1)
O
(
1
)
得到组合数，用快速幂会慢接近
9
9
9
倍
code：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int maxn = 1e6 + 9;
const int mod = 1e9 + 7;
ll n, m, t;
ll fac[maxn], inv[maxn];
ll C(ll n, ll m)
{
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
bool check(ll a, ll b, ll x)
{
if(!x) return 0;
while(x){
if(!(x % 10 == a || x % 10 == b))
return false;
x /= 10;
}return true;
}
void work()
{
fac[0] = inv[0] = 1;
fac[1] = inv[1] = 1;
for(int i = 2; i <= 1e6; ++i)
fac[i] = fac[i-1] * i % mod,
inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
for(int i = 1; i <= 1e6; ++i)
inv[i] = inv[i-1] * inv[i] % mod;
ll a, b;
cin >> a >> b >> n;
ll ans = 0;
for(int i = 0; i <= n; ++i)
{
ll t = a * i + (n - i) * b;
if(check(a, b, t))
ans = (ans + C(n, i)) % mod;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0);
// int TT;cin>>TT;while(TT--)
work();
return 0;
}
G题
D. Count the Arrays—-cf链接
题意：
计算由多少个数组满足以下特征
长度为
n
n
n
每个元素都属于
[
1
,
m
]
[1,m]
[
1
,
m
]
数组中必须有一个元素出现两次
数组中存在一个索引
i
i
i
，满足
j
<
i
j<i
j
<
i
时
a
j
<
a
j
+
1
a_j<a_{j+1}
a
j
<
a
j
+
1
和
j
>
=
i
j>=i
j
>
=
i
时
a
j
>
a
j
+
1
a_j>a_{j+1}
a
j
>
a
j
+
1
思路：
每个数组由
n
−
1
n-1
n
−
1
个数组成，首先从
m
m
m
个元素中选出
n
−
1
n-1
n
−
1
个，即
C
m
n
−
1
C_m^{n-1}
C
m
n
−
1
然后会有一个数出现两次，但不能是最大值，因此再乘以
C
n
−
2
1
C_{n-2}^1
C
n
−
2
1
除了出现两次以外的数，其他数只出现一次，要么出现在左边，要么出现在右边，因此
n
−
2
n-2
n
−
2
个数中的剩下
n
−
3
n-3
n
−
3
个数，可以选择右边或左边，乘以
2
n
−
3
2^{n-3}
2
n
−
3
那么答案就是
C
m
n
−
1
∗
(
n
−
2
)
∗
2
n
−
3
(
n
>
=
3
)
C_m^{n-1}*(n-2)*2^{n-3}(n>=3)
C
m
n
−
1
∗
(
n
−
2
)
∗
2
n
−
3
(
n
>
=
3
)
最后乘的
2
n
−
3
2^{n-3}
2
n
−
3
也可以这么理解：
我们枚举最大值的位置，第二个空，第三个空 … 倒数第二个空
每次确定完最大值位置后，其他数可以选择放左边或者右边，我们选出放左边的数的个数
C
n
−
3
0
,
C
n
−
3
1
.
.
.
C
n
−
3
n
−
3
C_{n-3}^0,C_{n-3}^1…C_{n-3}^{n-3}
C
n
−
3
0
,
C
n
−
3
1
.
.
.
C
n
−
3
n
−
3
，加起来即为
2
n
−
3
2^{n-3}
2
n
−
3
显然
n
<
=
2
n<=2
n
<
=
2
是存在的，特判掉即可
code：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 998244353;
ll n, m, t;
ll fac[maxn], inv[maxn];
ll C(ll n, ll m)
{
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
ll q_pow(ll a, ll n, ll ans = 1){
while(n){
if(n & 1) ans=ans*a%mod;a=a*a%mod;n>>=1;
}return ans;
}
void work()
{
fac[0] = inv[0] = 1;
fac[1] = inv[1] = 1;
for(int i = 2; i <= maxn - 9; ++i)
fac[i] = fac[i-1] * i % mod,
inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
for(int i = 1; i <= maxn - 9; ++i)
inv[i] = inv[i-1] * inv[i] % mod;
cin >> n >> m;
if(n <= 2) cout << 0 << endl;
else cout << C(m, n - 1) * (n - 2) % mod * q_pow(2, n - 3) % mod;
}
int main()
{
ios::sync_with_stdio(0);
// int TT;cin>>TT;while(TT--)
work();
return 0;
}
H题
思路：
dfs+计数
从
x
(
∈
[
0
,
9
]
)
x(\in [0,9])
x
(
∈
[
0
,
9
]
)
中每次选出
i
(
∈
n
u
m
[
x
]
)
i(\in num[x])
i
(
∈
n
u
m
[
x
]
)
个，然后统计个数即可
说说如何统计个数
不考虑
0
0
0
为前导对答案的影响，答案即为
c
n
t
!
A
[
0
]
!
∗
A
[
1
]
!
∗
.
.
.
∗
A
[
9
]
(
A
[
i
]
是
数
字
i
出
现
的
次
数
)
\frac{cnt!}{A[0]!*A[1]!*…*A[9]}(A[i]是数字i出现的次数)
A
[
0
]
!
∗
A
[
1
]
!
∗
.
.
.
∗
A
[
9
]
c
n
t
!
(
A
[
i
]
是
数
字
i
出
现
的
次
数
)
，
c
n
t
cnt
c
n
t
为选择的数的个数
然后减去
0
0
0
为前导的情况
0
0
0
为前导的个数占总数的
A
[
0
]
c
n
t
\frac{A[0]}{cnt}
c
n
t
A
[
0
]
，这个具体为什么我也不清楚，模拟一下确实是这个比例
122
,
212
,
221
122,212,221
1
2
2
,
2
1
2
,
2
2
1
三个排列，
2
2
2
的个数为
2
2
2
，
2
2
2
开头的排列占
2
3
\frac{2}{3}
3
2
1222
,
2122
,
2212
,
2221
1222,2122,2212,2221
1
2
2
2
,
2
1
2
2
,
2
2
1
2
,
2
2
2
1
四个排列，同理
现在知道为啥是这个比例了，这个排列显然是去重后的，如果不去重，那么三个数的全排列就是6，那么以
x
x
x
开头的排列的个数，占比是
A
[
x
]
c
n
t
\frac{A[x]}{cnt}
c
n
t
A
[
x
]
，但是这种排列进行去重之后这个比例是不变的。
code：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 998244353;
ll n, m, t;
ll fac[30], num[30], tmpnum[30];
ll ans;
void dfs(int x) //从0~9寻找各数字的出现
{
if(x == 10){
int cnt = 0; //cnt记录所有数字的个数
for(int i = 0; i < 10; ++i)
cnt += tmpnum[i];
ll p = fac[cnt];// 选出来这种方案的全排列
for(int i = 0; i < 10; ++i)
p /= fac[tmpnum[i]];
// sum! / （A[0]!*A[1]!*...*A[9]!）
if(tmpnum[0] >= 1)// 减去0为前导的情况
p -= (p * tmpnum[0] / cnt);
ans += p;
return;
}
for(int i = 1; i <= num[x]; ++i)
tmpnum[x] = i, dfs(x + 1);
if(num[x] == 0) dfs(x + 1);
}
void work()
{
fac[0] = 1;
for(int i = 1; i <= 25; ++i)
fac[i] = fac[i-1] * i;
cin >> n;
while(n){
num[n%10]++;
n /= 10;
}
dfs(0);
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(0);
// int TT;cin>>TT;while(TT--)
work();
return 0;
}
还有两道暂时不补了，感觉好难