AGC013E Placing Squares

发表于 | 分类于

Description

对于\(1\ldots n\)，你需要将其划分为若干段。并且有\(m\)个限制，其中第\(i\)个\(X_i\)的含义是\(X_i\)和\(X_i+1\)不能划分在同一段里。

我们称一种方案的权值为所有段长度的平方的积，求所有合法划分方案的权值。

\(1\leq n\leq 10^9, 0\leq m\leq 10^5, 1\leq X_1<X_2<\ldots < X_m < n\)。

Solution

数数难，难于上青天！

一个段长度的平方是一个很毒瘤的东西。但是注意到我们可以把这个东西转化为在该段放两个不一样的球（可以放到一块）的方案数，因此搞成了一个很通常的DP……

接下来的话矩乘优化一下就好了。顺便注意一下在隔断的地方不能拆段，所以有两种转移方程。

Code

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using ll = long long;
const ll ha = 1000000007LL;
typedef ll Mat[3][3];
void mat_mul(Mat A, Mat B, int n, int m, int p, Mat &res) {
  static Mat C; memset(C, 0, sizeof(C));
  for(int i = 0; i < n; i ++) {
    for(int j = 0; j < p; j ++) {
      for(int k = 0; k < m; k ++) {
        C[i][j] += A[i][k] * B[k][j] % ha;
        if(C[i][j] >= ha) C[i][j] -= ha;
      }
    }
  }
  memcpy(res, C, sizeof(C));
}
void mat_pow(Mat A, int n, int c, Mat &res) {
  static Mat C, a; memset(C, 0, sizeof(C));
  for(int i = 0; i < n; i ++) C[i][i] = 1;
  memcpy(a, A, sizeof(a));
  while(c) {
    if(1 & c) mat_mul(C, a, n, n, n, C);
    mat_mul(a, a, n, n, n, a); c >>= 1;
  }
  memcpy(res, C, sizeof(C));
}

Mat A, C, T, B;
std::vector<int> V;
int main() {
  int n, m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int x; scanf("%d", &x);
    V.push_back(x);
  }
  V.push_back(n);
  int las = 0;
  A[0][0] = 1;
  A[1][0] = 2; A[1][1] = 1;
  A[2][0] = A[2][1] = A[2][2] = 1;
  C[0][0] = C[0][2] = C[1][1] = C[2][2] = 1;
  mat_mul(C, A, 3, 3, 3, C);
  ll ans = 1LL;
  B[0][0] = 1; B[1][0] = B[2][0] = 0;
  for(int x : V) {
    mat_pow(C, 3, x - las - 1, T);
    mat_mul(A, T, 3, 3, 3, T);
    mat_mul(T, B, 3, 3, 1, B);
    las = x;
  }
  printf("%lld\n", B[2][0]);
  return 0;
}