BZOJ 2323 - [ZJOI2011]细胞

#dp #矩阵快速幂

Published on 2016-05-23

题目地址
题目太长了，不放描述。

分析

此题题意非常复杂，要求的是不同的稳定结构的种类数量。不难发现，每个对密码串的分割是独立的，即只要第一次对密码串的分割不一样，那么后面怎么退化都不可能一样。我们先看一个对密码串的分割后，退化会有多少种情况。

退化的实质就是分组，根据分割可以得到共 $k$ 个小球，则问题变为给小球分组，只能相邻的在一组，且一组内必须有至少 2 个球，问有多少种分球方案。设 $g_i$ 为 $i$ 个球的合法方案，那么有初始值：

g_1 = 0, g_2 = 1, g_3 = 1, g_4 = 1

考虑递推关系，假设前 $n - 1$ 个球都放好了，正在放第 $n$ 个球，那么第 $n$ 个球可以附在最后一组中，所以 $g_n$ 一定有 $g_{n - 1}$ 。但是发现算少了，因为如果附在最后一组，原先 $n - 1$ 个球的方案中最后一组就可以只有一个球了，这是我们没算到的，所以补上这种情况，让 $n$ 和 $n - 1$ 成为单独的一组，那么有 $g_{n - 2}$ 种方案。

所以 $g_n = g_{n - 1} + g_{n - 2}$ ，不难发现，这像极了 Fibonacci 数，对应关系为：

\begin{aligned} F_0 &= F_1 = 1, F_n = F_{n - 1} + F_{n - 2}\\ g_1 &= 0, g_n = F_{n - 2} \end{aligned}

显然是可以用矩阵快速幂求出来的，一个比较方便的方法是记，则 $F_n = (K^n)_{2, 2}$ ，即 $F_n$ 为 $K^n$ 的右下角元素。

所以问题转变为：给出一个长度为 $n(1\le n \le 1000)$ 的数字串，只包含 $1$ 到 $9$ ，将数字串分成不同的子串（显然这样的分法有 $2^{(n-1)}$ 种），将所有子串看做 10 进制的数字加起来得到该种分法下的和 $\mathrm{sum}_i$ ，求：

\sum F_{\mathrm{sum}_i - 2}

明显不能暴力求，设为处理前个字符的方案数。为了方便运算，我们直接设为一个矩阵，它的右下角为处理前个字符的方案数。再设我们的字符串为。则有。

再次考虑递推关系，假设正在处理第 $n$ 个字符，前面的都算出来了，那么枚举第 $n$ 个字符和谁一组，则有递推关系：

f_n = \sum\limits_{1\le j\le n}f_{j - 1} * K^{\mathrm{num}_{[i, j]}}

而 $K^{\mathrm{num}_{[i, j]}}$ 这个可以拆位，预处理出 $K$ 的 10 次幂搞定。为了方便，直接令，这样就非常方便的求了，答案是 $(F_n)_{2, 2}$ 。

代码

//  Created by Sengxian on 5/23/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2323 dp + 矩阵快速幂
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 1000 + 3, maxs = 2, modu = 1000000007;
ll t[maxs][maxs];

#define mod(i) ((i) % modu)

struct Matrix {
    int n, m;
    ll a[maxs][maxs];
    Matrix(int n = 0, int m = 0): n(n), m(m) {memset(a, 0, sizeof a);}
    ll* operator [] (int i) {return *(a + i);}
    void operator += (const Matrix &m1) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                (a[i][j] += m1.a[i][j]) %= modu;
    }
    void operator *= (const Matrix &m1) {
        memset(t, 0, sizeof t);
        for (int i = 0; i < n; ++i)
            for (int k = 0; k < m; ++k)
                for (int j = 0; j < m1.m; ++j)
                    (t[i][j] += mod((ll)a[i][k] * m1.a[k][j])) %= modu;
        memcpy(a, t, sizeof t);
        m = m1.m;
    }
    Matrix operator * (const Matrix &m1) const {
        Matrix ne(n, m1.m);
        for (int i = 0; i < n; ++i)
            for (int k = 0; k < m; ++k)
                for (int j = 0; j < m1.m; ++j)
                    (ne[i][j] += mod((ll)a[i][k] * m1.a[k][j])) %= modu;
        return ne;
    }
    Matrix power(ll v) {
        Matrix res(n, n), t = *this;
        for (int i = 0; i < n; ++i) res[i][i] = 1;
        while (v) {
            if (v & 1) res *= t;
            t *= t;
            v >>= 1;
        }
        return res;
    }
    void print() {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j)
                cout << a[i][j] << ' ';
            cout << endl;
        }
    }
}f[maxn], K, binPowers[maxn];

char str[maxn];
int n, s[maxn];

void solve() {
    for (int i = 1; i <= n; ++i) {
        Matrix tmp(2, 2); tmp[0][0] = tmp[1][1] = 1;
        f[i] = Matrix(2, 2);    
        for (int j = i; j > 0; --j) {
            tmp *= binPowers[i - j + 1].power(s[j]);
            f[i] += f[j - 1] * tmp;
        }
    }
    printf("%lld\n", (f[n][1][1] + modu) % modu);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), scanf("%s", str + 1);
    for (int i = 1; i <= n; ++i) s[i] = str[i] - '0';

    K = Matrix(2, 2);
    K[0][1] = 1, K[1][0] = 1, K[1][1] = 1;

    binPowers[1] = K;
    for (int i = 2; i < maxn; ++i) binPowers[i] = binPowers[i - 1].power(10);

    f[0] = Matrix(2, 2);
    f[0][0][0] = -1, f[0][0][1] = 1, f[0][1][0] = 1;
    f[0] = f[0].power(2); //K ^ (-2)
    f[0].print();
    solve();
    return 0;
}

BZOJ 4332 - [JSOI2012]分零食 BZOJ 3242 - [Noi2013]快餐店

Sengxian's Blog

BZOJ 2323 - [ZJOI2011]细胞

分析

代码