bzoj 2323: [ZJOI2011]细胞

题外话：好像欠了很多题解。。。有空再补吧

题意：

给你一个长度为$n$的数列，将它切成若干段，每段的质量相等，然后再按每段上的数字组成的十进制数$x$把这一段分成$x$个小段，所有小段平分这一段的质量。分完之后所有小段排成一行，某些相邻的小段粘在一起，使得没有小段两边都没有和旁边的粘起来。两种结构被认为相同，当且仅当他们拥有相同个数的小段，从头到尾每个小段的质量相同，并且从头到尾每对相邻小段之间的连接情况相同。问最终有多少种结构。

题解：

首先我们想一想，如果知道了分成多少小段，最终会有多少种情况。设$f_{i, 0/1}$表示前$i$个小段，第$i$个小段有没有连着左边的小段。那么$$
f_{i, 0} = f_{i - 1, 1} \\\
f_{i, 1} = f_{i - 1, 0} + f_{i - 1, 1}

g_i = \sum_{j = 1}^i g_j \times d^{\overline{s_{j \ldots i}}}

$$
还有个问题，$\overline{s_{j \ldots i}}$超级大。我们可以一位一位搞，预处理出$d$的$10^k$次幂，然后直接乘起来就好。

代码：

#include <bits/stdc++.h>
using namespace std;

const int mod = 1000000007;
int n;
char s[1010];
struct matrix
{
    int x, y;
    long long a[2][2];
    matrix() : a() {}
    long long *operator[](int x) { return a[x]; }
} one, base[1010], f[1010];

matrix operator+(matrix x, matrix y)
{
    for (int i = 0; i < x.x; i++)
        for (int j = 0; j < x.y; j++)
            (x[i][j] += y[i][j]) %= mod;
    return x;
}
matrix operator*(matrix x, matrix y)
{
    matrix ans;
    ans.x = x.x;
    ans.y = y.y;
    for (int i = 0; i < ans.x; i++)
        for (int j = 0; j < ans.y; j++)
            for (int k = 0; k < y.x; k++)
                (ans[i][j] += x[i][k] * y[k][j] % mod) %= mod;
    return ans;
}
matrix Pow(matrix x, int y)
{
    matrix ans = one;
    for (int i = 0; i < y; i++)
        ans = ans * x;
    return ans;
}
int main()
{
    scanf("%d%s", &n, s + 1);
    one.x = one.y = 2;
    one[0][0] = one[1][1] = 1;
    base[0].x = base[0].y = 2;
    base[0][0][1] = base[0][1][0] = base[0][1][1] = 1;
    for (int i = 1; i < n; i++)
    {
        matrix hh = base[i - 1];
        base[i] = hh = hh * hh;
        hh = hh * hh;
        hh = hh * hh;
        base[i] = base[i] * hh;
    }
    f[0].x = 1;
    f[0].y = 2;
    f[0][0][0] = -1;
    f[0][0][1] = 1;
    for (int i = 1; i <= n; i++)
    {
        f[i].x = 1;
        f[i].y = 2;
        matrix hh = one;
        for (int j = i; j > 0; j--)
        {
            hh = hh * Pow(base[i - j], s[j] - '0');
            f[i] = f[i] + f[j - 1] * hh;
        }
    }
    printf("%lld\n", (f[n][0][1] + mod) % mod);
}