Theme NexT works best with JavaScript enabled

2019 牛客暑期多校训练营第九场题解

本文包括 2019 牛客暑期多校训练营第九场的题面与题解。

A - The power of Fibonacci

题目描述

Amy asks Mr. B problem A. Please help Mr. B to solve the following problem.

Let $ Fi $ be fibonacci number.

$ F_0 = 0, F_1 = 1, F_i = F_{i-1} + F_{i-2} $

Given n and m, please calculate $ \sum_{i = 0}^n F_i^m $

As the answer might be very large, output it module $ 1000000000 $ .

输入描述

The first and only line contains two integers $ n, m(1 \leq n \leq 1000000000, 1 \leq m \leq 1000) $ .

输出描述

Output a single integer, the answer module $ 1000000000 $ .

示例1

输入

1
5 5

输出

1
3402

说明

$ 0^5 + 1^5 + 1^5 + 2^5 + 3^5 + 5^5 = 3402 $

示例2

输入

1
10 10

输出

1
696237975

说明

Don’t forget to mod $ 1000000000 $

示例3

输入

1
1000000000 1000

输出

1
641796875

说明

Time is precious.

题解

题意

给定 $ n,m $ ,求斐波那契数列的 $ m $ 次方的前 $ n $ 项和,答案对 $ 10^9 $ 取模。

解法

可以知道斐波那契数列在取模意义下是有循环节的。

但是模 $ 10^9 $ 时循环节为 $ 1.5 \times 10^8 $ ,实在过大。

考虑到中国剩余定理,求 $ ans \% p $ ,可以求 $ ans\% p_1 $ 和 $ ans \% p_2 $ (要求 $ p_1 \times p_2 = p $ ,且 $ p_1 $ 和 $ p_2 $ 互素),合并回去即可得到答案。

$ 10^9 = 2^9 \times 5^9 $ ,可以拆分为 $ 512 $ 和 $ 1953125 $ 。这样可以知道斐波那契数列分别在模 $ 512 $ 和 $ 1953125 $ 意义下的循环节,易知两循环节分别为 $ 768 $ 和 $ 7812500 $ 。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll p = 1e9;
const ll p1 = 512, loop1 = 768, inv_p1 = 1537323;
const ll p2 = 1953125, loop2 = 7812500, inv_p2 = 109;
ll Qpow(ll x, ll n, ll p) {
ll s = 1;
while (n) {
if (n & 1) s = s * x % p;
x = x * x % p;
n >>= 1;
}
return s;
}
ll fi(ll n, ll m, ll loop, ll p) {
if (n < 3) return n;
ll k = n % loop, s = 2, tmp = k < 3 ? k : 0;
ll a = 1, b = 1, c;
for (int i = 3; i <= loop; i++) {
c = (a + b) % p;
a = b, b = c;
s = (s + Qpow(c, m, p)) % p;
if (i == k) tmp = s;
}
return (s * (n / loop) % p + tmp) % p;
}

int main() {
ll n, m;
scanf("%lld%lld", &n, &m);
ll ans1 = fi(n, m, loop1, p1), ans2 = fi(n, m, loop2, p2);
ll ans = (ans1 * p2 % p * inv_p2 % p + ans2 * p1 % p * inv_p1 % p) % p;
printf("%lld\n", ans);
return 0;
}

B - Quadratic equation

题目描述

Amy asks Mr. B problem B. Please help Mr. B to solve the following problem.

Let p = $ 1000000007 $ .

Given two integers $ b $ and $ c $ , please find two integers $ x $ and $ y $ $ (0 \leq x \leq y < p) $ , such that

$ (x + y) \bmod p = b $

$ (x \times y) \bmod p = c $

输入描述

The first line contains an integer $ t $ , which is the number of test cases ( $ 1 \leq t \leq 10 $ ).

In the following $ t $ lines, each line contains two integers $ b $ and $ c $ ( $ 0 \leq b, c < p $ ).

输出描述

For each test case, please output $ x, y $ in one line.

If there is a solution, because $ x \leq y $ , the solution is unique.

If there is no solution, please output -1, -1 .

示例1

输入

1
2
3
4
5
6
7
8
9
10
11
10
4 4
5 6
10 10
10 25
20000 100000000
0 5
3 6
220 284
0 1
1000000000 1000000000

输出

1
2
3
4
5
6
7
8
9
10
2 2
2 3
-1 -1
5 5
10000 10000
474848249 525151758
352077071 647922939
448762649 551237578
-1 -1
366417496 633582504

题解

题意

给定 $ x,y $ 在 $ \% p $ ( $ p=10^9 + 7 $ )意义下的和 $ b $ 与积 $ c $ ,求 $ x $ 和 $ y $ 。

解法

已知 $ 0 \leq x + y <2 \times p $ ,那么有两种情况, $ b = x + y $ 或者 $ b = x + y - p $ .

将两式中任意一式代入 $ (x \times y) \bmod p = c $ 均可得到 $ (b - x) \times x = k \times p +c (k \in Z) $ .

该函数是个关于 $ x $ 的二次函数,若该函数有整数解,那么有 $ \Delta = b ^ 2 - 4 \times ( k \times p + c ) $ 为完全平方数。

令 $ s ^ 2 = b ^ 2 - 4 \times ( k \times p + c ) $ ,则该问题转化为二次剩余问题。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll Qpow(ll x, ll n) {
ll s = 1;
while (n) {
if (n & 1) s = s * x % mod;
x = x * x % mod;
n >>= 1;
}
return s;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
ll b, c;
scanf("%lld%lld", &b, &c);
ll delta = (b * b - 4 * c + mod) % mod;
if (Qpow(delta, (mod - 1) / 2) == mod - 1)
puts("-1 -1");
else {
ll a = Qpow(delta, ((mod + 1) / 2 + 1) / 2);
ll x = ((b - a + mod) * Qpow(2, mod - 2)) % mod;
ll y = (b + mod - x) % mod;
printf("%lld %lld\n", min(x, y), max(x, y));
}
}
return 0;
}

C - Inversions of all permutations

题目描述

Amy asks Mr. B problem C. Please help Mr. B to solve the following problem.

Given an array $ a_i $ with length $ n $ , and $ a $ base $ b $ .

For each permutation $ \{ r_i \} $ of $ \{ a_i \} $ , we count the number of inversions as $ t ( \{ r_i \} ) $ .

Please calculate $ \sum_{\{r_i\} \text{is a permutation of} \{a_i\}} b^{t(\{r_i\})} $

As the answer might be very large, please output it modulo $ 1000000007 $ .

输入描述

The first line contains $ n, b (n \leq 100000, 1 \leq b \leq 1000000000) $ .

The second line contains $ n $ integers, which are $ a_i (0 \leq a_i \leq 100000) $ .

输出描述

Output the answer in one line.

As the answer might be very large, please output it modulo $ 1000000007 $ .

示例1

输入

1
2
3 10
1 2 3

输出

1
1221

说明

There are $ 6 $ permutations. The number of inversions are $ 0, 1, 1, 2, 2, 3 $ .

示例2

输入

1
2
4 10
1 1 2 2

输出

1
11211

说明

There are $ 6 $ permutations. The number of inversions are $ 0, 1, 2, 2, 3, 4 $ .

If there are duplicate integers in $ \{ a_i \} $ , the number of permutations are less than the factorial of $ n $ ( $ n! $ ).

示例3

输入

1
2
10 10
1 2 3 4 5 6 7 8 9 10

输出

1
291457966

说明

Don’t forget to mod $ 1000000007 $ .

D - Knapsack Cryptosystem

题目描述

Amy asks Mr. B problem D. Please help Mr. B to solve the following problem.

Amy wants to crack Merkle–Hellman knapsack cryptosystem. Please help it.

Given an array $ \{ a_i \} $ with length $ n $ , and the sum $ s $ .

Please find a subset of $ \{ a_i \} $ , such that the sum of the subset is $ s $ .

For more details about Merkle–Hellman knapsack cryptosystem Please read
https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
https://blog.nowcoder.net/n/66ec16042de7421ea87619a72683f807

Because of some reason, you might not be able to open Wikipedia.

Whether you read it or not, this problem is solvable.

输入描述

The first line contains two integers, which are $ n $ ( $ 1 \leq n \leq 36 $ ) and $ s $ ( $ 0 \leq s < 9e18 $ )

The second line contains n integers, which are $ \{ a_i \} $ ( $ 0 < a_i < 2e17 $ ).

$ \{ a_i \} $ is generated like in the Merkle–Hellman knapsack cryptosystem, so there exists a solution and the solution is unique.

Also, according to the algorithm, for any subset sum s, if there exists a solution, then the solution is unique.

输出描述

Output a $ 01 $ sequence.

If the $ i $ -th digit is $ 1 $ , then $ a_i $ is in the subset.

If the $ i $ -th digit is $ 0 $ , then $ a_i $ is not in the subset.

示例1

输入

1
2
8 1129
295 592 301 14 28 353 120 236

输出

1
01100001

说明

This is the example in Wikipedia.

示例2

输入

1
2
36 68719476735
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368

输出

1
111111111111111111111111111111111111

题解

题意

经典的Merkle–Hellman背包加密算法,给定该加法背包的公钥和密文,求解。

解法

考虑到公钥长度不超过 $ 36 $ ,对该公钥分两组,各 $ 18 $ 个,分别跑背包,再验证即可。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define N 41
#define lll __int128
lll a[N], s;
template <typename _tp>
inline void read(_tp& x) {
char ch = getchar(), sgn = 0;
x = 0;
while (ch ^ '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') ch = getchar(), sgn = 1;
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
if (sgn) x = -x;
}
inline void Print(lll x, int s) {
for (int i = 0; i < s; i++) printf("%d", !!(x & (1 << i)));
}
map<lll, lll> mp, mq;
int main() {
int n;
read(n), read(s);
for (int i = 0; i < n; i++) read(a[i]);
int p = n / 2, q = n - p;
for (int i = 0; i < (1 << p); i++) {
lll t = 0;
for (int j = 0; j < p; j++)
if (i & (1 << j)) t += a[j];
mp[t] = i + 1;
}
for (int i = 0; i < (1 << q); i++) {
lll t = 0;
for (int j = 0; j < q; j++)
if (i & (1 << j)) t += a[j + p];
mq[t] = i + 1;
}
for (auto it = mp.begin(); it != mp.end(); it++)
if (mq[s - (*it).first]) {
Print((*it).second - 1, p);
Print(mq[s - (*it).first] - 1, q);
break;
}
return 0;
}

E - All men are brothers

题目描述

Amy asks Mr. B problem E. Please help Mr. B to solve the following problem.

There are $ n $ people, who don’t know each other at the beginning.

There are m turns. In each turn, $ 2 $ of them will make friends with each other.

The friend relation is mutual and transitive.

If A is a friend of B, then B is also a friend of A.

For example, if A is a friend of B, B is a friend of C, then A and C are friends.

At the beginning and after each turn, please calculate the number of ways to select four people from, such that any two of these four are not friends.

输入描述

The first line contains two integers, $ n $ and $ m $ ( $ n \leq 100000, m \leq 200000 $ ), which are the number of people, and the number of turns.

In the following $ m $ lines, the $ i $ -th line contains two integers $ x $ and $ y $ ( $ 1 \leq x \leq n, 1 \leq y \leq n, x \neq y $ ), which means the $ x $ -th person and the $ y $ -th person make friends in the $ i $ -th turn.

The $ x $ -th person and $ y $ -th person might make friends in several turns.

输出描述

Output $ m+1 $ lines, each line contains an integer, which is the number of quadruples.

Output at the beginning and after each turn, so there are $ m+1 $ lines.

示例1

输入

1
2
3
4
5
6
7
6 6
1 2
3 4
4 5
3 5
3 6
2 4

输出

1
2
3
4
5
6
7
15
9
4
0
0
0
0

示例2

输入

1
100000 0

输出

1
4166416671249975000

说明

Don’t use int.

题解

题意

有 $ n $ 个人,开始互不是朋友。给定 $ m $ 次操作,每次操作使两人成为朋友。已知朋友关系具有传递性。问每次操作后从所有人中任选四人,这四人两两不是朋友的选择方案数。

解法

用并查集维护朋友关系网,每次让两个人交朋友等价于让两个集合合并,每次合并计算对答案的贡献。

注意计算初值的过程中时容易爆long long,所以需要特判一下。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
int f[N], num[N], n, m;
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool Union(int a, int b) {
int x = find(a), y = find(b);
if (x == y) return false;
num[x] += num[y], f[y] = x;
return true;
}
int main() {
scanf("%d%d", &n, &m);
ll ans = n % 4 == 3 ? (ll)n * (n - 1) / 2 * (n - 2) / 3 * ((n - 3) / 4)
: (ll)n * (n - 1) / 2 * (n - 2) / 6 * (n - 3) / 2;
printf("%lld\n", ans);
ll sums = n;
for (int i = 1; i <= n; ++i) f[i] = i, num[i] = 1;
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
int fx = find(x), fy = find(y);
if (fx != fy) {
ll c1 = num[fx], c2 = num[fy];
num[fx] += num[fy], f[fy] = fx;
ll t = (n - c1 - c2);
sums -= c1 * c1 + c2 * c2;
ans -= c1 * c2 * (t * t - sums) / 2;
sums += (c1 + c2) * (c1 + c2);
}
printf("%lld\n", ans);
}
return 0;
}

F - Birthday Reminders

题目描述

Today is Tomori’s birthday! Usually, people get many birthday wishes on social media, but Tomori has decided to hide her birthday on social media, and thus does not expect many (if any) wishes from her friends.

Tomori has N friends. Some of the friends actually remembered her birthday! For each friend iii, he or she will remember Tomori’s birthday at time $ t_i $ and give her a birthday wish at that instant (or not remember her birthday at all if $ t_i = -1 $ ).

Some of Tomori’s friends are very considerate however, and decides to remind others about her birthday. Friend $ i $ will remind friend $ p_i $ about Tomori’s birthday after he or she has wished her. Formally, if Friend $ i $ gave Tomori a birthday wish at time $ t $ , then he or she will remind friend $ p_i $ to give Tomori a birthday wish at time $ t+1 $ (and friend $ p_i $ will give her a birthday wish at time $ t+1 $ and remind friend $ p_{p_i} $ at time $ t+2 $ and so on, assuming that they have not already gave her a birthday wish). The sequence $ p_i $ forms a permutation, i.e. each friend will be reminded by exactly one friend. Note that $ p_i = i $ is possible, which means that the friend will not remind anyone about Tomori’s birthday after sending their wish.

The day is over and at the end of the day, Tomori receives the wish from Friend i at time $ b_i $ (if $ b_i = -1 $ , it means that friend $ i $ never wished her for her birthday). Note that $ b_i $ might not be equal to $ t_i $ as he or she might be reminded by another friend at an earlier time.

Tomori receives the wishes, but she actually can’t distinguish between her friends, so she only knows the number of wishes she received at each particular time. Now, she wonders, over all possible permutations $ \{ p_i \} $ , how many possible different days she could have experienced. Two permutations $ p, q $ correspond to different days if at some point of time, the number of friends who wished Tomori was different.

输入描述

The first line of input contains a single integer $ N $ ( $ 1 \leq N \leq 100 $ ).

The next line of input contains N space-separated integers, the i-th of which denotes $ t_i $ ( $ t_i = -1 $ or $ 1 \leq ti \leq 100 $ ).

输出描述

Output a single integer, the number of different days Tomori could have experienced. Since the answer might be too large, output it modulo $ 1000000007 $ .

示例1

输入

1
2
3
-1 2 1

输出

1
3

说明

There are 6 possible permutations.

If $ p = \{1, 2, 3\} $ , then $ b = \{-1, 2, 1\} $ .

If $ p = \{1, 3, 2\} $ , then $ b = \{-1, 2, 1\} $ .

If $ p = \{2, 1, 3\} $ , then $ b = \{3, 2, 1\} $ .

If $ p = \{2, 3, 1\} $ , then $ b = \{2, 2, 1\} $ .

If $ p = \{3, 1, 2\} $ , then $ b = \{3, 2, 1\} $ .

If $ p = \{3, 2, 1\} $ , then $ b = \{2, 2, 1\} $ .

There are $ 3 $ distinct possible days Tomori could have experienced.

Please note that even if we have $ b = \{1, 2, 2\} $ with some permutation, it is considered the same as $ b = \{2, 2, 1\} $ , since Tomori can’t distinguish between her friends.

G - Checkers

题目描述

There are $ N $ black checker pieces on the coordinate plane. The $ i $ -th checker piece is located at point $ (X_{i}, Y_{i}) $ . You are playing a new type of game with these checker pieces.

A move is defined as follows :

Place a white checker piece $ W $ at some coordinate $ (2x, y) $ where $ x, y $ are integers. While there exist a black checker piece $ B $ at distance exactly $ 1 $ from $ W $ , you may choose to capture $ B $ by moving $ W $ to the symmetric point of its current position with respect to $ B $ , and remove $ B $ . Note that multiple checker pieces may occupy the same point at the same time. Once no such operation is possible or you choose to stop performing such operation, W is removed.

Each black checker piece has a $ \frac{1}{2} $ probability of getting removed before the game starts. What is the expected minimum number of moves required to complete the game? Let E be this expected value. It can be proven that $ E \cdot 2^{N} $ is an integer. Output $ E \cdot 2^{N} \bmod 1000000007 $

输入描述

The first line of input contains a single integer $ N $ ( $ 1 \leq N \leq 600 $ ).

The next $ N $ lines contains $ 2 $ space-separated integers $ X_i, Y_i $ ( $ 0 \leq X_i \leq 99, 0 \leq Y_i \leq 5 $ ), denoting the coordinates of the checker pieces.

输出描述

Output a single integer, the value of $ E \cdot 2^{N} \bmod 1000000007 $ .

示例1

输入

1
2
3
2
1 2
2 3

输出

1
3

H - Cutting Bamboos

题目描述

There are $ n $ bamboos arranged in a line. The $ i $ -th bamboo from the left has height $ h_{i} $ .

You are given $ q $ queries of the type $ (l, r, x, y) $ . For each query $ (l, r, x, y) $ we consider only the $ l $ -th to $ r $ -th bamboo inclusive. We want to make $ y $ horizontal cuts through these bamboos, such that after each cut, the total length of bamboo cut is the same, and after all $ y $ cuts there is no bamboo left. For example, if there are $ 3 $ bamboos of height $ 3, 4, 5 $ respectively and $ y = 4 $ . The first cut should be at height $ 3 $ , after which the heights of the bamboos are $ 3, 3, 3 $ respectively and the total amount of bamboo cut is $ 0 + 1 + 2 = 3 $ . Then, the next $ 3 $ cuts should be at height $ 2, 1, 0 $ respectively. You want to find out what is the height the $ x $ -th cut is performed.

Note that after each query, the bamboos are not actually cut, so the heights of the bamboos remain constant after each query.

输入描述

The first line of input contains two space-separated integers $ n, q $ ( $ 1 \leq n \leq 200000, 1 \leq q \leq 100000 $ ).

The next line of input contains $ n $ space-separated integers, the $ i $ -th of which denotes $ h_i $ , the height of the $ i $ -th bamboo ( $ 1 \leq h_i \leq 100000 $ ).

The next $ q $ lines of input contains $ 4 $ space-separated integers each, denoting $ l, r, x, y $ ( $ 1 \leq l \leq r \leq n, 1 \leq x \leq y \leq 10^9 $ ).

输出描述

Output q lines of real numbers, the $ i $ -th line contains the answer to the $ i $ -th query. Your answer will be accepted if its absolute or relative error is less than $ 10^{-6} $ .

示例1

输入

1
2
3
4
5
6
5 4
3 5 1 7 4
2 4 3 5
1 4 4 9
1 3 1999 101111
2 2 1 1

输出

1
2
3
4
2.100000005215406
2.629629638046026
4.822066854685545
0.000000026077032

说明

For the first query, we only consider the bamboos of height $ 5, 1, 7 $ .

The first cut should be at height $ 4.7 $ , the total amount of bamboo obtained is $ 0.3 + 0 + 2.3 = 2.6 $ .

The second cut should be at height $ 3.4 $ , the total amount of bamboo obtained is $ 1.3 + 0 + 1.3 = 2.6 $ .

The third cut should be at height $ 2.1 $ , the total amount of bamboo obtained is $ 1.3 + 0 + 1.3 = 2.6 $ .

The fourth cut should be at height $ \dfrac{13}{15} $ , the total amount of bamboo obtained is $ \dfrac{37}{30} + \dfrac{2}{15} + \dfrac{37}{30} = 2.6 $ .

The fifth cut should be at height $ 0 $ , the total amount of bamboo obtained is $ \dfrac{13}{15} + \dfrac{13}{15} + \dfrac{13}{15} = 2.6 $ .

Note that the output values are not exact, but are within the precision requirements.

题解

题意

有 $ n $ 棵竹子,给定它们的初始高度。接着有 $ q $ 次操作,每次操作给定四个参数 $ l,r,x,y $ ,表示将区间 $ [l,r] $ 的竹子的高度全部砍到零。一共要砍 $ y $ 次,且这 $ y $ 次砍伐每次需要设定一个高度,然后将所有高度高于设定高度的竹子全部砍到设定高度,要求每次砍掉的竹子的长度和相等。问你该过程中砍 $ x $ 次后该区间内竹子的高度。

解法

每次统计该区间 $ [l,r] $ 内竹子总高度 $ s $ ,可知每次需要砍掉的高度为 $ \dfrac{s}{y} $ ,第 $ x $ 次砍伐后就砍掉了 $ \dfrac{s \times x}{y} $ 。已知了高度之和,只需二分高度即可。用主席树维护区间内竹子的高度。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 200010
#define M 100000
#define eps 1e-8
int n, q, cnt, l, r, x, y;
int root[N];
ll sum1, sum2, sum[N];
struct node {
int l, r;
ll sum1, sum2;
} tree[N * 40];
void update(int l, int r, int& x, int y, int pos) {
tree[++cnt] = tree[y], tree[cnt].sum1 += 1, tree[cnt].sum2 += pos, x = cnt;
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid)
update(l, mid, tree[x].l, tree[y].l, pos);
else
update(mid + 1, r, tree[x].r, tree[x].r, pos);
}
void query(int l, int r, int x, int y, double pos) {
if (l == r) {
if (pos - l >= eps) {
sum1 += tree[y].sum1 - tree[x].sum1;
sum2 += tree[y].sum2 - tree[x].sum2;
}
return;
}
int mid = (l + r) >> 1;
if (mid - pos > eps)
query(l, mid, tree[x].l, tree[y].l, pos);
else {
sum1 += tree[tree[y].l].sum1 - tree[tree[x].l].sum1;
sum2 += tree[tree[y].l].sum2 - tree[tree[x].l].sum2;
query(mid + 1, r, tree[x].r, tree[y].r, pos);
}
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) {
scanf("%d", &x);
sum[i] = sum[i - 1] + x;
update(0, M, root[i], root[i - 1], x);
}
while (q--) {
scanf("%d%d%d%d", &l, &r, &x, &y);
double len = (double)(sum[r] - sum[l - 1]) / y * x;
double ub = M, lb = 0.0, mid, ans = 0.0;
for (int i = 0; i < 100; ++i) {
mid = (ub + lb) / 2;
sum1 = sum2 = 0;
query(0, M, root[l - 1], root[r], mid);
double tot = (double)(sum[r] - sum[l - 1] - sum2);
double big = (double)(r - l + 1 - sum1);
if (tot - big * mid - len > eps)
lb = mid, ans = mid;
else
ub = mid;
}
printf("%.7f\n", ans);
}
return 0;
}

I - KM and M

题目描述

Find the value of $ \displaystyle\sum_{k = 1}^{N} ((kM) \& M) \bmod (10^{9} + 7)k=1 $ ,where $ \& $ denotes the bitwise AND operator.

输入描述

The first and only line of input contains two space-separated integers $ N, M $ ( $ 1 \leq N \leq 10^18, 1 \leq M \leq 10^11 $ ).

输出描述

Output a single integer, the answer to the problem.

示例1

输入

1
4 6

输出

1
12

说明

The sum is $ 6 + 4 + 2 + 0 = 12 $ .

题解

题意

给定 $ N,M $ ,求解 $ \displaystyle \sum_{k=1}^{N}((kM)\&M)) $

解法

考虑第 $ i $ 位的贡献, 显然为 $ \lfloor \dfrac{kM}{2^i} \rfloor $ 为奇数的个数再乘上 $ 2^i $ ,即 $ 2^i(\sum \ \lfloor \dfrac{kM}{2^i} \rfloor −2\sum \lfloor \dfrac{kM}{2^{i+1}} \rfloor) $ , 可以用类欧几里得求出。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define INV ((mod + 1) / 2)
typedef long long ll;
ll S(ll a, ll b, ll c, ll n) {
if (a == 0) return 0;
if (a >= c || b >= c) {
ll x = S(a % c, b % c, c, n),
y = ((a / c) % mod * (n % mod) % mod * ((n + 1) % mod) % mod * INV +
b / c % mod * ((n + 1) % mod) + x) %
mod;
return (y + mod) % mod;
}
ll m = ((__int128)a * n + b) / c, x = S(c, c - b - 1, a, m - 1),
y = ((__int128)n * m - x) % mod;
return (y + mod) % mod;
}
int main() {
ll n, m;
scanf("%lld%lld", &n, &m);
ll ans = 0;
for (ll p = 1, loc = 0; p <= m; p *= 2, loc++) {
if (m & (1LL << loc)) {
ll k = (S(m, 0, p, n) - 2 * S(m, 0, 2 * p, n)) % mod,
s = p % mod * (k + mod) % mod;
ans = (ans + s + mod) % mod;
}
}
printf("%lld\n", ans);
return 0;
}

J - Symmetrical Painting

题目描述

Initially, the entire coordinate plane is colored white.

$ N $ rectangles were painted black. The $ i $ -th rectangle has bottom-left corner $ (i-1, L_i) $ and top-right corner $ (i,R_i) $ for $ 1 \le i \le n $ . You want to paint some of the black area white so that the remaining black part has a horizontal axis of symmetry. Find the maximum possible area of the remaining black part.

输入描述

The first line of input contains a single integer $ N $ ( $ 1 \leq N \leq 300000 $ ), denoting the number of rectangles.

The next $ N $ lines of input contain two space-separated integers each, denoting $ L_i, R_i $ ( $ 1 \leq Li < Ri \leq 10^9 $ ).

输出描述

Output a single integer, the answer to the problem.

示例1

输入

1
2
3
4
3
1 5
4 7
2 3

输出

1
4

说明

It is optimal to paint second rectangle entirely white and a rectangle with bottom-left corner $ (0, 4) $ and top-right corner $ (1, 5) $ white. Then, the remaining black figure has axis of symmetry at $ y = 2.5 $ . The remaining black area is $ 4 $ .

题解

题意

给定二维平面上的 $ n $ 个矩形,左下角 $ (i−1, L_i) $ , 右上角 $ (i, R_i) $ 。要求确定一条线 $ l $ 平行于 $ x $ 轴,保留这些矩形关于 $ l $ 对称的部分,删去不对称的部分,问最大的对称图形的面积。

解法

易知对称轴 $ l $ 高度必为某矩形的中线。

那么将这 $ n $ 个矩形按照下边高度排序,枚举中线即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 900010
ll n, cnt, a, b;
struct Node {
ll a, b;
} P[N];
bool cmp(Node x, Node y) { return x.a < y.a; }
int main() {
scanf("%lld", &n);
while (n--) {
scanf("%lld%lld", &a, &b);
P[++cnt] = {a <<= 1, 1}, P[++cnt] = {b <<= 1, 1},
P[++cnt] = {(a + b) >> 1, -2};
}
sort(P + 1, P + cnt + 1, cmp);
ll ans = 0, pre = 0, res = 0;
for (int i = 1; i < cnt; i++)
pre += P[i].b, res += (P[i + 1].a - P[i].a) * pre, ans = max(ans, res);
printf("%lld\n", ans);
return 0;
}