pdf版题面 在线提交（需要权限）

题目

问题描述

乐滋滋经常参加各种拍卖会，前不久，他收到了来自滋滋国最大的商店——奥义商店的拍卖会邀请函。

为了让拍卖会看起来更加奥妙重重，奥义商店设置了一个极为复杂的拍卖规则：

一共$n$个物品排成一排，第$i$个物品价格是$v_i$。对于一次拍卖，商店会指定$t$种颜色，并对每种颜色指定一个数目$c_j$满足$\sum_{j = 1}^{t} c_j = n - 1$，另外还会指定一个下标$k$和一个公差$d$。

买家需要给第$k$个物品染上一种颜色（在$t$种颜色中选择一种）。

接着，把剩下的$n - 1$个物品随机染成$t$种颜色之一，并保证这$n - 1$个物品中第$j$种颜色的恰好有$c_j$个。

买家需要购买的物品按这样的方式计算：找到$k$所在的最长的以$d$为公差的等差数列$a_x = k + xd(x \in [L, R], L \leq 0 \leq R)$满足其中所有物品都与第$k$个物品同色。买家需要买下这个等差数列中的所有物品，显然花费就是$\sum_{x = L}^{R} v_{k + xd}$。

乐滋滋最近出现了点“经济危机”，希望你能帮他给第$k$个物品选择合适的颜色，以此来最小化他花费的期望，你只需要输出这个期望即可。

当然商品的价格是可能出现变动的，你需要维护这些变化。

输入格式

第一行两个整数$n,m$表示商品数和操作数。

第二行$n$个整数$v_i$表示每个商品的初始价格。

接下来$m$行，每行代表一个操作，每行第一个数表示操作类型：

1. 接下来输入两个数$x, y$表示把$v_x$修改为$y$。

2. 接下来先输入三个数$t, k, d$，再输入$t$个数$c_j$，表示一次询问。

注意任意两次询问是互相独立的，询问不会买走物品。

输出格式

对于每个询问输出一个实数表示最少期望花费，保留$4$位小数。

样例输入1

3 3
1 1 1
2 2 1 1 1 1
1 2 2
2 2 3 1 1 1

点击这里下载

样例输出1

1.5000
2.0000

点击这里下载

样例输入2

点击这里下载

样例输出2

点击这里下载

数据范围与约定

对于$10\%$的数据：$n, m \leq 10$；

对于$20\%$的数据：$n, m \leq 100$；

对于$30\%$的数据：$n, m \leq 1000$；

另有$20\%$的数据满足：$t = 1$；

另有$20\%$的数据满足：$k = d = 1$；

对于全部数据：$1 \leq n, m \leq 10^5$;$1 \leq v_i, y \leq 10^4$;$1 \leq x, k, d \leq n$;$1 \leq t \leq n - 1$;$\sum t \leq 2 \times 10^5$，对于全部数据满足$v_i$和$y$均随机生成。

题解

我们先考虑$t = 1$的情况。这时所有位置都是同色的，当给定了公差$d$和固定下标$k$时，只需要求出所有满足$d | (x - k)$的$v_x$之和。这里可以根据$d$的大小分别考虑：

• 若$d > \sqrt{n}$，我们直接暴力修改、统计即可，时间复杂度为$O(\sqrt{n})$。
• 若$d \leq \sqrt{n}$，我们用一个二维数组$f[i][j]$记录下来所有满足下标$x \equiv j({\rm mod}\ i)$的$v_x$之和，这样在查询的时候就可以直接输出$f[d][k\ {\rm mod}\ d]$的值，而修改时至多只用修改到$\sqrt{n}$个位置上的数，因此单次操作的时间复杂度仍然是$O(\sqrt{n})$。

综上，$t=1$的情况可以在$O(\sqrt{n})$的时间内进行每次操作。

而当$t > 1$的时候，染色方案是随机的，不难发现要使得最终的花费最小，规定的位置一定要染上出现次数最少的一种颜色，不妨记作颜色$p$。当然，之后并不能暴力枚举所有可能的染色方案，我们只能换一种思路。考虑位置$x$满足$d | (x - k)$，设$y = \frac{|x - k|}{d} + 1$，那么这个位置对答案产生贡献的概率应该是$x, x + d, x + 2d, \cdots, k$（或$x, x - d, x -2d, \cdots, k$）这些位置均染成指定颜色的概率。但这个值怎么求呢？

首先，总的染色方案共有$\dfrac{(t - 1)!}{\prod c_j!}$种，而这些位置都钦定为颜色$p$之后，染色方案还有$\dfrac{(t - y - 1)!}{\prod_{j \neq t} c_j!(c_p - y)!}$种，因此概率
$$P = \frac{(t - 1)!}{\prod c_j!} \times \frac{\prod_{j \neq t} c_j!(c_p - y)!}{(t - y - 1)!} = \frac{(t - 1)!(c_p - y)!}{c_p!(t - y - 1)!} = \frac{\prod_{i = t - y}^{t - 1}i}{\prod_{j = c_p - y + 1}^{c_p}j}$$
这显然是可以在运行过程中递推出来的，之后乘上该处价格就是期望花费，求和即可。但是这样子的时间复杂度是$O(n^2)$的。

这里有一个小Trick——当$y$很大时上式无限接近$0$，因此当判断出值小于某极小数时直接停止运算即可。考虑题目的精度要求，从原位置出发，左右扩展$100$个数左右就可以保证精确了。

时间复杂度为$O(m(\sqrt{n} + 100))$，可以通过此题。

代码

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

#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
#define MAXN 100010
int readint()
{
	int x = 0, c;
	while (!isdigit(c = getchar()));
	do
		x = x * 10 + c - '0';
	while (isdigit(c = getchar()));
	return x;
}
int n, m;
int v[MAXN];
int sum[1000][1000];
int main()
{
	freopen("lzz.in", "r", stdin);
	freopen("lzz.out", "w", stdout);
	n = readint();
	m = readint();
	for (int i = 1;i <= n; i++)
		v[i] = readint();
	int size = (int)sqrt(n);
	for (int i = 1; i <= size; i++)
		for (int j = 1; j <= n; j++)
			sum[i][j % i] += v[j];
	for (int i = 0; i < m; i++)
	{
		int op = readint();
		if (op == 1)
		{
			int x = readint();
			int y = readint();
			for (int j = 1; j <= size; j++)
				sum[j][x % j] += y - v[x];
			v[x] = y;
		}
		else
		{
			int t = readint();
			int k = readint();
			int d = readint();
			if (t > 1)
			{
				int ls = 200000;
				for (int i = 1; i <= t; i++)
				{
					int c = readint();
					ls = min(ls, c);
				}
				double ans = v[k];
				double cnt = 1;
				for (int l = -1; k + l * d > 0; l--)
				{
					if (-l > ls)
						break;
					cnt = cnt * (ls + l + 1);
					cnt = cnt / (n + l);
					if (cnt <= 1e-15)
						break;
					ans += cnt * v[k + l * d];
				}
				cnt = 1;
				for (int r = 1; k + r * d <= n; r++)
				{
					if (r > ls)
						break;
					cnt = cnt * (ls - r + 1);
					cnt = cnt / (n - r);
					if (cnt <= 1e-15)
						break;
					ans += cnt * v[k + r * d];
				}
				printf("%.4f\n", ans);
			}
			else
			{
				int c = readint();
				double ans = 0;
				if (d > size)
				{
					for (int i = k; i > 0; i -= d)
						ans += v[i];
					for (int i = k + d; i <= n; i += d)
						ans += v[i];
				}
				else
					ans = sum[d][k % d];
				printf("%.4lf\n", ans);
			}
		}
	}
	return 0;
}