CF2020A
题目链接
题意
一次操作可以从$n$减掉$k$的幂次，问最少操作数使得$n=0$。
解法
把$N$变成$k$进制，然后输出各位的和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int Main()
{
int n, k;
read(n, k);
if (k == 1)
return printf("%d\n", n), 0;
int ans = 0;
while (n)
{
ans += n % k;
n /= k;
}
std::cout << ans << std::endl;
return 0;
}
|
CF2020B
题目链接
题意
假设有$n$个灯，一开始是亮的。从1开始枚举$i$，每次操作$i$的倍数的灯（亮变暗，暗变亮），最终有$k$个灯是亮的。求最小的$n$能达成恰好$k$个灯亮着
解法
最终变暗的灯，一定是有奇数个约数。
把一个数$x$分解质因数得到$x=\prod p_i^{e_i}$，那么$d(x)=\sum(e_i+1)$。
如果$d(x)$是奇数，等价于$e_i$都是偶数。这样显然$x$是完全平方数。
于是$N$以内能亮的灯就是$N-\sqrt N$个，这是个单调的函数，因此可以二分得到$N$。
注意整数开方的精度。WA了一发TNND。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int Main()
{
ll k;
read(k);
ll l = 1, r = k * 2;
while (l <= r)
{
ll mid = (l + r) >> 1;
if (mid - (ll)sqrtl(mid) < k)
l = mid + 1;
else
r = mid - 1;
}
std::cout << l << std::endl;
return 0;
}
|
CF2020C
题目链接
题意
给出$b,c,d$，问是否存在$a$使得$(a|b) - (a \& c) = d$
解法
如果$a$中有一个位置是1，那么$a|b$这一位必然是1，$a\&c$这一位可能是1也可能是0。
如果$a$中有一个位置是0，那么$a|b$这一位可能是0也可能是1，但是$a\&c$必然是0。
于是不存在一个位使得在这个位上$(a|b)<(a\&c)$，那么做差等价于做异或。
这样减法变成了各位独立的二进制异或操作，可以枚举$a$每一位的值判定结果是否等于$d$。
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
|
int Main()
{
ll b, c, d;
read(b, c, d);
ll a = 0;
for (int i = 0; i < 61; ++i)
{
int dbit = (d >> i) & 1;
int cbit = (c >> i) & 1;
int bbit = (b >> i) & 1;
bool found = false;
for (int abit = 0; abit < 2; ++abit)
{
if ((abit | bbit) ^ (cbit & abit) == dbit)
{
a |= ((ll)abit << i);
found = true;
}
}
if (!found)
return printf("-1\n"), 0;
}
std::cout << a << std::endl;
return 0;
}
|
CF2020D
题目链接
题意
有$n$个点，$m$个操作。
每个操作给出三个数$a,k,d$，连接$a+d, a+2d, a+3d, …, a+kd$。
问最终一共多少个连通块
解法
一开始被迷惑了然后上了个厕所。
上的时候发现，最终的图里面，每个点不重复的边最多就10条。那么可以考虑对于每个点$u$，维护一个长为10的数组$e$，$e[i]$如果不为0，可以认为$i$向$i+d$有边相连。
那么原来的加边操作，相当于在$+d$的域上做了一个区间加，用差分维护一下即可。
最终边数不超过$10n$。
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
|
struct DSU
{
public:
DSU() : n(0) {}
explicit DSU(int _n) : n(_n), parent_or_size(_n + 1, -1) {}
int merge(int a, int b)
{
int x = leader(a), y = leader(b);
if (x == y)
return x;
if (-parent_or_size[x] < -parent_or_size[y])
std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b)
{
return leader(a) == leader(b);
}
int leader(int a)
{
if (parent_or_size[a] < 0)
return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a)
{
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups()
{
std::vector<int> leader_buf(n + 1), group_size(n + 1);
for (int i = 1; i <= n; i++)
{
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(n);
for (int i = 1; i <= n; i++)
{
result[i].reserve(group_size[i]);
}
for (int i = 1; i <= n; i++)
{
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int> &v)
{ return v.empty(); }),
result.end());
return result;
}
private:
int n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
int Main()
{
int n, m;
read(n, m);
std::vector<std::array<int, 11>> tag(n + 1);
DSU dsu(n);
for (int i = 1; i <= m; ++i)
{
int a, d, k;
read(a, d, k);
tag[a][d] += 1;
tag[a + k * d][d] -= 1;
}
for (int i = 1; i <= n; ++i)
{
for (int d = 1; d <= 10; ++d)
{
if (i - d >= 1)
tag[i][d] += tag[i - d][d];
if (tag[i][d] > 0 && i + d <= n)
dsu.merge(i, i + d);
}
}
int ans = 0;
for (int i = 1; i <= n; ++i)
ans += dsu.leader(i) == i;
printf("%d\n", ans);
return 0;
}
|
CF2020E
题目链接
题意
有$n$个数$a[i]$，每个数被选中的概率是$p[i]$。
把这些数按概率扔到一个多重集合$S$里。设$f(S)$是集合的异或和，求$E(f(S)^2)$
解法
由于平方不是一个线性变换，那么集合的异或平方值的期望不能等于集合异或期望值的平方。
所以单独考虑集合异或值在平方之后的式子。
一个二进制数可以考虑为各个1的加和。那么平方之后就是各个位的平方和+2倍每两位的乘积和。
和的形式可以利用期望线性性处理，因此考虑对求各位平方的期望以及每两位乘积的期望。
由期望公式，收益是一定的，因此这等价于求一个概率。
某一位$k$为1，等价于集合中的数，$k$位为1的个数是奇数。而每个数可选可不选，这似乎是一个背包。
对于固定的一位$k$，用$dp[i][j]$表示前$i$个数，奇偶性为$j$时的概率，背包转移一下即可。
每两位乘积的期望就是依次考虑两个位，用一个长为2的二进制串分别表示这两位的奇偶性，同样是一个背包。
最后根据期望公式加和一下就ok。
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
|
{
int n;
read(n);
std::vector<int> a(n + 1);
std::vector<modint> prob(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
modint inv = modint(10000).inv();
for (int i = 1; i <= n; ++i)
{
int v;
read(v);
prob[i] = v * inv;
}
std::vector<std::array<modint, 2>> dp1(n + 1);
modint ans = 0;
for (int p = 0; p < 10; ++p)
{
dp1.assign(n + 1, {});
dp1[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
if (a[i] >> p & 1)
{
dp1[i][0] = dp1[i - 1][0] * (1 - prob[i]) + dp1[i - 1][1] * prob[i];
dp1[i][1] = dp1[i - 1][1] * (1 - prob[i]) + dp1[i - 1][0] * prob[i];
}
else
dp1[i] = dp1[i - 1];
}
// printf("p = %d, dp = %d\n", p, dp1[n][1]);
ans += (1 << (p + p)) * dp1[n][1];
}
std::vector<std::array<modint, 4>> dp2(n + 1);
for (int p = 0; p < 10; ++p)
for (int q = p + 1; q < 10; ++q)
{
dp2.assign(n + 1, {});
dp2[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
int mask = 0;
if (a[i] >> p & 1)
mask |= 2;
if (a[i] >> q & 1)
mask |= 1;
for (int pmask = 0; pmask < 4; ++pmask)
{
dp2[i][pmask] += dp2[i - 1][pmask] * (1 - prob[i]);
dp2[i][pmask ^ mask] += dp2[i - 1][pmask] * prob[i];
}
}
ans += 2 * (1 << p) * (1 << q) * dp2[n][3];
}
printf("%d\n", ans);
return 0;
}
|
CF2020F
题目链接
题意
假设有一棵树，根节点的点权是$x$。
第$i$层的点，把点权的约数作为新点的点权扩展到自己的子节点；假设一共做$d$次，最终的叶子节点是$f(x,d)$。
给出一个$n\leq 10^9$，求$\sum_{i=1}^n f(i^k, d)$
$k,d\leq 10^5$
解法
大概看了一下数据规模和给出函数形式，由于跟约数个数函数相关，感觉是积性函数求和问题。
可以打个表验证一下对于固定的$k$和$d$，这个函数是不是积性函数。
经过打表可以确定这是积性函数。那么积性函数求和问题，先考虑min25筛，因为$d=1$的情况是典题，可以用min25筛来做。
其实这个地方我是先看到$d=1$是min25筛，接下来走偏了，考虑从$d$去推$d+1$的做法。VP的时候懒了没去打表，实际上应该先打个表。
对于质数$p$，$f(p^k,d)$的形式应该是每层都是$p^e$。每一步可以考虑直接落到最后下一步，或者考虑降幂落到下一步。
设$d$个变量，$x[i]$表示在第$i$步的降幂，那么显然$x[i]\geq 0$，且$\sum_{i=1}^d x[i]\leq k$。
这个不等式解的数量就是$f(p^k, d)$。
$\sum_{i=1}^d x[i]\leq k$等价于$\sum_{i=1}^d x[i] = k - t(t\geq 0)$。
将$t$移动到左边，并且让它成为$x[d+1]$。于是式子变成
$$\sum_{i=1}^{d+1} x[i]=k(x[i]\geq 0)$$求这个方程解的数量显然隔板法得到$C(k+d,d)$。
那么质数部分就是一个常量，显然是完全积性函数，满足min25筛。
考虑质数的指数部分，$f(p^{tk}, d)=C(kt+d,d)$，可以$O(1)$得到，也满足min25筛。
于是套一个min25筛就行了。
注意组合数可能会取到几百万。
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
|
template <int m, std::enable_if_t<(1 <= m)> * = nullptr>
struct static_modint
{
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v)
{
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
static_modint(long long v)
{
long long x = (long long)(v % (long long)(umod()));
if (x < 0)
x += umod();
_v = (unsigned int)(x);
}
static_modint(int v)
{
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint &operator++()
{
_v++;
if (_v == umod())
_v = 0;
return *this;
}
mint &operator--()
{
if (_v == 0)
_v = umod();
_v--;
return *this;
}
mint operator++(int)
{
mint result = *this;
++*this;
return result;
}
mint operator--(int)
{
mint result = *this;
--*this;
return result;
}
mint &operator+=(const mint &rhs)
{
_v += rhs._v;
if (_v >= umod())
_v -= umod();
return *this;
}
mint &operator-=(const mint &rhs)
{
_v -= rhs._v;
if (_v >= umod())
_v += umod();
return *this;
}
mint &operator*=(const mint &rhs)
{
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const
{
assert(0 <= n);
mint x = *this, r = 1;
while (n)
{
if (n & 1)
r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const
{
assert(_v);
return pow(umod() - 2);
}
friend mint operator+(const mint &lhs, const mint &rhs)
{
return mint(lhs) += rhs;
}
friend mint operator-(const mint &lhs, const mint &rhs)
{
return mint(lhs) -= rhs;
}
friend mint operator*(const mint &lhs, const mint &rhs)
{
return mint(lhs) *= rhs;
}
friend mint operator/(const mint &lhs, const mint &rhs)
{
return mint(lhs) /= rhs;
}
friend bool operator==(const mint &lhs, const mint &rhs)
{
return lhs._v == rhs._v;
}
friend bool operator!=(const mint &lhs, const mint &rhs)
{
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
// static constexpr bool prime = internal::is_prime<m>;
};
template <class T>
struct Combinatorics
{
int n = 0;
std::vector<T> fac;
std::vector<T> invfac;
std::vector<T> inv;
Combinatorics(int _n = 0) : fac{1}, invfac{1}, inv{0}
{
init(_n);
}
void init(int m)
{
if (n >= m)
return;
fac.resize(m + 1), invfac.resize(m + 1), inv.resize(m + 1);
for (int i = n + 1; i <= m; ++i)
fac[i] = fac[i - 1] * i;
invfac[m] = fac[m].inv();
for (int i = m; i > n + 1; --i)
invfac[i - 1] = invfac[i] * i;
for (int i = m; i > n; --i)
inv[i] = invfac[i] * fac[i - 1];
n = m;
}
T operator()(int x, int y)
{
if (x < y)
return 0;
return fac[x] * invfac[y] * invfac[x - y];
}
};
using modint = static_modint<(int)1e9 + 7>;
auto sieve(int mx)
{
std::vector minp(mx + 1, 0);
std::vector<int> prime;
for (int i = 2; i <= mx; ++i)
{
if (minp[i] == 0)
prime.push_back(i), minp[i] = i;
for (int p : prime)
{
if (1ll * i * p > mx)
break;
minp[i * p] = p;
if (i % p == 0)
break;
}
}
return prime;
}
int Main()
{
static Combinatorics<modint> combinatorics(4e6 + 5);
ll n, k, d;
read(n, k, d);
const int sqrtn = std::sqrt(n);
auto prime = sieve(sqrtn);
std::vector<ll> v;
for (ll l = 1, r = 1; l <= n; l = r + 1)
{
v.push_back(n / l);
r = n / (n / l);
}
auto idx = [&](ll x) -> int
{
if (x <= sqrtn)
return v.size() - x;
else
return n / x - 1;
};
std::vector<modint> sp(v.size());
for (int i = 0; i < v.size(); ++i)
{
int x = v[i];
sp[i] = x - 1;
}
std::vector<modint> sum(prime.size() + 1);
for (int i = 1; i <= prime.size(); ++i)
{
int p = prime[i - 1];
for (int n = 0; n < v.size(); ++n)
{
ll x = v[n];
if (x < 1ll * p * p)
break;
sp[n] -= (sp[idx(x / p)] - sum[i - 1]);
}
sum[i] = sum[i - 1] + 1;
}
for (int i = 0; i < v.size(); ++i)
sp[i] *= combinatorics(k + d, d);
for (int i = 1; i <= prime.size(); ++i)
sum[i] *= combinatorics(k + d, d);
std::vector<modint> sc(v.size());
for (int i = prime.size(); i >= 1; --i)
{
int p = prime[i - 1];
for (int n = 0; n < v.size(); ++n)
{
ll x = v[n];
if (1ll * p * p > x)
break;
ll pw = p;
for (int e = 1; x / pw >= p; ++e)
{
modint f = combinatorics(e * k + d, d);
int j = idx(x / pw);
sc[n] += f * (sc[j] + sp[j] - sum[i]);
pw *= p;
if (pw <= x)
sc[n] += combinatorics((e + 1) * k + d, d);
}
}
}
modint ans = sp[0] + sc[0] + 1;
printf("%d\n", ans);
return 0;
}
|
![Featured image of post [VP]Codeforces Round 976 A~F](/p/vpcodeforces-round-976-a~f/background_hu_61a0e603618c3f6f.png)