一开始做的时候花较长时间推了一个假做法，写完暴力发现做法假了之后就不想再想了，比较可惜。
这种题能不能给个强一点的样例解释，样例解释的序列都只要操作 次（
考虑操作 之后 和 不变化的条件： 你发现两个数对应的条件是一样的，也就是说，如果 ，那么都会变化，否则都不会变。这点可以引申出，是不会被这次操作影响的，即序列中所有数的和不变。
如果变化了，容易发现 。
设 表示 收敛之后的结果。
那么如果 ，那么 。反过来说，如果 ，那么整个过程中就不会操作 。
这一点我没归纳出来，看来还需要多分析终态的性质，不仅仅是操作过程的性质。
如果我们能找到最小的 使得
，那么， 和 是完全无关的！
因为题目只关心 ，所以我们可以列出关于 的若干个方程，尝试解出 。 设 。
那么 。
但我们并不知道
的取值是多少，怎么办呢？
我们可以将 取遍 ，每次都解一遍方程，然后让解的最小值作为 !
接下来说明这为什么是对的。
首先 肯定 ，因为肯定存在一个 满足 。
另一方面，如果 ，那么在
之前肯定有一个 ，而
不变，所以为了跨度更大只能减小初值。故此时有 。
那么 等价于
，也就是说，对于 ，都有 。这个条件与原限制等价。
有了这个结论就可以直接背包来做 F1 了。
考虑
F2，唯一的不同在于询问很多，但是注意到有很多的询问都是没用的。
具体地，如果 过小，使得 全为 都满足条件，那么答案显然为 。
如果 过大，使得 都不满足条件（即存在 ），那么答案显然为 。
考虑算出这两个界的具体值，设 。
那么在 之外的 都可以用上面的判断解决。
否则，不同的 只有 个，对这些 预处理答案即可。
非常 math 的一道题，哪怕是 F1，严谨的分析过程也较长。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5,M = 2e4 + 5,P = 1e9 + 7;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
int n,c[N],b[N];
int f[M],g[M];
int sb[N];
map<int,int> Ans;
inline int Solve(int x)
{
for(int i = 0;i < M;i++) f[i] = 0,g[i] = 1;
int sc = 0;
for(int i = 1;i <= n;i++)
{
int lim = i * x + sb[i];sc += c[i];
for(int j = max(0,lim);j < M;j++)
f[j] = (g[j] - (j - c[i] - 1 >= 0 ? g[j - c[i] - 1] : 0) + P) % P;
g[0] = f[0];f[0] = 0;
for(int j = 1;j < M;j++)
g[j] = (g[j - 1] + f[j]) % P,f[j] = 0;
}
return g[M - 1];
}
int main()
{
cin >> n;int m = 0,mul = 1;
for(int i = 1;i <= n;i++) cin >> c[i],m = max(m,c[i]),mul = 1ll * mul * (c[i] + 1) % P;
for(int i = 1;i < n;i++) cin >> b[i];
for(int i = 1;i <= n;i++)
for(int j = 1;j < i;j++)
sb[i] += (i - j) * b[j];
double lb = 0,rb = 1e9;
for(int i = 1;i <= n;i++)
lb = min(lb,-1.0 * sb[i] / i),
rb = min(rb,1.0 * (i * m - sb[i]) / i);
lb = ceil(lb);rb = floor(rb);
for(int i = lb;i <= rb;i++) Ans[i] = Solve(i);
int q,x;
cin >> q;
while(q--)
{
cin >> x;
if(lb <= x && x <= rb) cout << Ans[x] << endl;
else if(x < lb) cout << mul << endl;
else cout << 0 << endl;
}
return 0;
}
|