[Codeforces 821E] Okabe and El Psy Kongroo

题目大意

在平面直角坐标系中,从 (0,0)(0, 0) 走到 (k,0)(k, 0) 。要求:

  • 每时每刻满足 x,y0x, y \geqslant 0
  • 每次只能从 (x,y)(x, y) 走到 (x+1,y+1)(x + 1, y + 1)(x+1,y)(x + 1, y)(x+1,y1)(x + 1, y - 1)
  • nn 条水平线段,用 (ai,bi,ci)(a_i, b_i, c_i) 表示线段 y=ci,(aixbi)y = c_i, (a_i \leqslant x \leqslant b_i) ,满足 bi=ai+1b_{i} = a_{i + 1}a1=0a_1 = 0。要求,对于任意 aixbia_i \leqslant x \leqslant b_iyciy \leqslant c_i

求方案数,答案对 1,000,000,0071,000,000,007 取模。

1n1001 \leqslant n \leqslant 100

1k1×10181 \leqslant k \leqslant 1 \times 10^{18}

0ai<bi1×10180ci150 \leqslant a_i < b_i \leqslant 1 \times 10^{18} \quad 0 \leqslant c_i \leqslant 15

题目链接

Codeforces 821E

题解

我本来一直没有写 CF 的题解,但这道题,犯了一个小错误导致 9-9 。。。

DP + 矩乘。

f(x,y)f(x, y) 表示走到 (x,y)(x, y) 的答案,转移为:

f(x,y)=f(x1,y1)+f(x1,y)+f(x1,y+1)f(x, y) = f(x - 1, y - 1) + f(x - 1, y) + f(x - 1, y + 1)

注意到 cc 很小、横坐标们很大,考虑矩乘优化(这个矩乘还是很好想的,相比某 KMP + 矩乘的题),完毕。

然后,当时我干了个什么呢?把矩阵快速幂的指数设成了 int ,一直没发现,于是就一直 TLE。。。 233333

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
template <typename T>
void read(T &x) {
char ch;
while ((ch = getchar()) > '9' || ch < '0');
x = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - '0';
}
const int MAXC = 16;
const int MAXN = 100;
const int MOD = 1000000007;
struct Matrix {
long long a[MAXC][MAXC];
Matrix(bool init = false) {
memset(a, 0, sizeof (a));
if (init) for (int i = 0; i < MAXC; i++) a[i][i] = 1;
}
friend Matrix operator*(const Matrix &a, const Matrix &b) {
Matrix res(false);
for (int i = 0; i < MAXC; i++) for (int k = 0; k < MAXC; k++) for (int j = 0; j < MAXC; j++)
(res(i, j) += a(i, k) * b(k, j) % MOD) %= MOD;
return res;
}
long long &operator()(int i, int j) {
return a[i][j];
}
long long operator()(int i, int j) const {
return a[i][j];
}
};
Matrix pow(Matrix a, long long n) {
Matrix res(true);
for (; n; n >>= 1, a = a * a) if (n & 1) res = res * a;
return res;
}
int main() {
int n;
long long k;
scanf("%d %lld", &n, &k);
Matrix init(false);
init(0, 0) = 1;
for (int i = 0; i < n; i++) {
long long a, b;
int c;
scanf("%lld %lld %d", &a, &b, &c);
if (a >= k) break;
for (int j = c + 1; j < MAXC; j++) init(j, 0) = 0;
if (c == 0) continue;
Matrix trans(false);
for (int j = 0; j <= c; j++) {
trans(j, j) = 1;
if (j) trans(j, j - 1) = 1;
if (j < c) trans(j, j + 1) = 1;
}
Matrix temp = pow(trans, std::min(b, k) - a);
init = temp * init;
}
printf("%lld\n", init(0, 0));
return 0;
}