HAOI2015 数字串拆分

未分类

枚举最后一个出现的数字来计算 $f(i)$，那么 $f(i)=\sum\limits_{j=1}^{m} f(i-j)$，很显然可以矩阵加速。设转移矩阵为 $d$，对于 $g(i)$，因为 $f(x+y)=f(x)d^y$，以及矩阵满足分配率，枚举最后一个断点，$g(i)=\sum g(j)d^{a[j+1,i]}$，$g(i)$ 表示的是所有 $f$ 矩阵的和，直接递推计算即可。总复杂度 $\mathcal O(n^2m^3)$。

#include <iostream>
#include <cstdio>
#include <cstring>
const int MAXN = 500;
const int MOD = 998244353;
int n, m;
char s[MAXN + 2];
struct Matrix {
  int a[6][6];
  Matrix() {
    memset(a, 0, sizeof(a));
  }
  friend Matrix operator* (const Matrix &lhs, const Matrix &rhs) {
    Matrix res;
    for (int i = 1; i <= m; ++i) 
      for (int j = 1; j <= m; ++j) 
        for (int k = 1; k <= m; ++k) 
          res.a[i][j] = (1LL * res.a[i][j] + 1LL * lhs.a[i][k] * rhs.a[k][j]) % MOD;
    return res;
  }
  friend Matrix operator+ (const Matrix &lhs, const Matrix &rhs) {
    Matrix res;
    for (int i = 1; i <= m; ++i) 
      for (int j = 1; j <= m; ++j) 
        res.a[i][j] = (lhs.a[i][j] + rhs.a[i][j]) % MOD;
    return res;
  }
  void out() {
    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= m; ++j) printf("%d ", a[i][j]);
      printf("\n");
    }
  }
  void init() {
    for (int i = 1; i <= m; ++i) a[i][i] = 1;
  }
} dp[MAXN | 1], d[MAXN | 1][10];
int main() {
  scanf("%s", s + 1);
  scanf("%d", &m);
  n = strlen(s + 1);
  for (int i = 1; i <= m; ++i) {
    d[0][1].a[i][m] = 1;
    if (i > 1) d[0][1].a[i][i - 1] = 1;
  }
  dp[0].a[1][m] = 1;
  for (int i = 0; i <= n; ++i) {
    for (int j = 1; j < 10; ++j) {
      if (i == 0 && j == 1) continue;
      if (j == 1) d[i][j] = d[i - 1][9] * d[i - 1][1];
      else d[i][j] = d[i][j - 1] * d[i][1];
    }
  }
  s[0] = '0';
  for (int i = 1; i <= n; ++i) {
    Matrix now;
    now.init();
    for (int j = i - 1; j >= 0; --j) {
      if (s[j + 1] != '0') {
        now = now * d[i - 1 - j][s[j + 1] - '0'];
      }
      dp[i] = dp[i] + (dp[j] * now);
    }
  }
  printf("%d\n", dp[n].a[1][m] % MOD);
  return 0;
}