题目描述
http://codeforces.com/contest/1467/problem/D
简要题意：给定一个长度 $n$ 的序列 $a_i$，现在有一个机器人，它可以任何点为起点，每次可以选择向左或向右移动一格，但不能离开 $[1,n]$，现在它会走 $k$ 步，定义一条路径的权值为机器人经过的所有点的点权和，点被多次经过算多次。现在有 $q$ 个询问，每次给定 $x,y$，修改 $a_x=y$，求机器人的所有路径的权值和
Solution
我们令 $f[i][j]$ 表示走了 $i$ 步在点 $j$ 的路径条数
注意到因为我们开始的起点是所有点且路径可逆，所以 $f[i][j]$ 同样可以表示从 $j$ 开始走 $i$ 步的方案数
那么所有路径中经过点 $j$ 的次数就是 $\sum_{i=0}^kf[i][j]\times f[k-i][j]$
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 <iostream>
#include <cstdio>
#define maxn 5010
#define maxm 100010
#define ll long long
using namespace std;
const int p = 1000000007;
int n, k, m, a[maxn];
int f[maxn][maxn], g[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k >> m;
for (int i = 1; i <= n; ++i) cin >> a[i], f[0][i] = 1;
for (int i = 1; i <= k; ++i)
for (int j = 1; j <= n; ++j) {
if (j > 1) f[i][j] = (f[i][j] + f[i - 1][j - 1]) % p;
if (j < n) f[i][j] = (f[i][j] + f[i - 1][j + 1]) % p;
}
for (int i = 0; i <= k; ++i)
for (int j = 1; j <= n; ++j) g[j] = (g[j] + (ll) f[i][j] * f[k - i][j]) % p;
ll ans = 0;
for (int i = 1; i <= n; ++i) ans = (ans + (ll) g[i] * a[i]) % p;
for (int i = 1; i <= m; ++i) {
int x, y; cin >> x >> y;
ans = (ans + (ll) g[x] * (y - a[x])) % p;
a[x] = y; cout << (ans + p) % p << "\n";
}
return 0;
}
|