Counting Arrays
原题链接
题意
设有数组 \(a\) ，每次可以删除其中 \(\gcd(a_i,i)=1\) 的位置，后方的元素前移。
最终可以将数组清空。
问：有多少个满足以下条件的数组？
- 元素个数不超过 \(n\) 。
- 元素数值是 \([1,m]\) 之间的整数。
- 有两种或以上的策略，可以将数组清空。
⭐rating: 1900
分析
有一种显而易见的策略，即每次选取第一个数，将其删除。这样的数组总共有 \(m^1+m^2+...+m^n=total\) 个。满足两种及以上的策略的数组也包含其中，此时只需要减去只满足一种策略的数组的数量即可。
只满足一种策略的数组的即为：在每次删除首个元素的过程中，始终没有其他位置 \(i>1\)，满足 \(\gcd(a_i,i)=1\)。
假设数组长度为 \(t\)。
- \(a_1\) 不受任何约束。
- \(a_2\) 在第一轮需要满足 \(\gcd(a_2,2)\neq 1\)。第二轮在首位，无约束。
- \(a_3\) 在第一轮需要满足 \(\gcd(a_3,3)\neq 1\)。第二轮在第二个位置上，还需要满足 \(\gcd(a_3,2)\neq 1\)。
- ……
- \(a_i\) 应该满足：对于任意的 \(2\le j\le i\)，有 \(\gcd(a_i,j)\neq 1\)。
我们只需要找出其中 \(a_1,a_2,…,a_t\) 的个数，将其相乘，得到的数去减 \(total\) 即为所求的答案。
求解个数时，对于长度为 \(i\) 的数组，我们定义 \(cur\) 为当前需要减去的数组个数，\(tmp\) 为当前需要的倍数。
- 当 \(i\) 为素数时，\(a_i\) 的限制与 \(a_{i+1}\) 不同，因此需要加上对于素数 \(i\) 的限制，即 \(tmp=tmp*i\)。\(cur\) 需要乘上 \(m\div tmp\)，再 \(total\) 减去 \(cur\)。
- 当 \(i\) 为合数时，假设有 \(x*y=i\)，那么 \(\gcd(a_i,x)\neq 1\)，就有 \(\gcd(a_i,i)\neq 1\)。即 \(tmp\) 不变。
具体可见代码。
代码
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
116 | #include <bits/stdc++.h>
using i64 = long long;
const int P = 998244353;
// assume -P <= x < 2P
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
Z(i64 x) : x(norm(x % P)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z &operator*=(const Z &rhs) {
x = i64(x) * rhs.x % P;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
friend std::istream &operator>>(std::istream &is, Z &a) {
i64 v;
is >> v;
a = Z(v);
return is;
}
friend std::ostream &operator<<(std::ostream &os, const Z &a) {
return os << a.val();
}
};
bool isprime(int x) {
if (x <= 1) return false;
for (int i = 2; i <= x / i; i++)
if (x % i == 0)
return false;
return true;
}
int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n;
i64 m;
std::cin >> n >> m;
Z total = 0;
for (int i = 1; i <= n; i++)
total += power(Z(m), i);
Z cur = 1;
for (int i = 1; i <= n && m; i++) {
if (isprime(i)) m /= i; // 此时的m为满足gcd!=1的数的个数
cur *= m;
total -= cur;
}
std::cout << total << '\n';
return 0;
}
|