ZJOI2011 细胞

题目:

  2222年,人类在银河系外的某颗星球上发现了生命,并且携带了一个细胞回到了地球。经过反复研究,人类已经完全掌握了这类细胞的发展规律:
  这种细胞最初的形态是“长条形”,一端是头,一端是尾,中间是躯干。细胞内部含有一列密码(你可以认为它是这种细胞的DNA)。密码是一个长度为n的数字串,且仅含有1~9这9种数字,沿着细胞的躯干从头到尾排列着。
  分裂成若干个球体,躯干将退化成丝状物,连接着相邻的球体。在分裂过程中,质量是均匀分布的。换句话说,若分裂成k个球体,每个球体的质量为原来的1/k。然而,密码的分布是不确定的。若分割成k个球体,密码会被切割成k段(每段长度至少为1),并按从头到尾的顺序分布在各个球体中。
  接下来,细胞会经历二次分裂。对于每个球体,其中会含有一小段密码(注意他是有序的),我们把它看作一个十进制的数T。这个球体会被分割成T个小球体,并排成一排,之间用躯干退化成的丝状物相连接,并且质量仍然是均匀分布的,每个小球体的质量都是原球体的1/T。至此,密码已经发挥了它的作用,便消失了。
  最后,细胞会进行变异。相邻小球体之间的丝状物可能会退化掉,这两个小球体便会以相切的方式直接连接。显然,二次分裂后,除两端外的每个小球体都有两段丝状物与其连接(头尾两端的小球体只有一段丝状物与其相连)。对于每个小球体,必须至少退化一段与其相连的丝状物,否则这个结构不稳定,会继续变异。
  现在,我们想知道,对于一个给定密码的细胞,总共有多少种稳定的结构。两种结构被认为相同,当且仅当他们拥有相同个数的小球体,从头到尾每个小球体的质量相同,并且从头到尾每对相邻小球体之间的连接方式相同(都是通过丝状物相连或都是通过相切直接相连)。你只需要回答这个结果 mod 1000000007即可。

思路:

  先随便手动划分一下发现如果只看球的大小,所有的划分方案都是不重的。所以最终答案就是每种划分方案的连接方案数之和。连接方案数用递推转移算一下会发现就是斐波那契数,所以要求的就变成了
  要求斐波那契数的第 项就很容易联想到矩阵上,所以就可以把答案表示成 。又因为矩阵满足 ,所以把矩阵作为 值进行转移,只要先 预处理一下每个区间组成的 即可,整体复杂度就是

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 1005, MOD = 1e9 + 7;

struct Matrix {
    int a[2][2], n, m;
    int* operator[] (int x) {return a[x];}
    Matrix() {mset(a, 0);}
    Matrix operator* (Matrix d) {
        Matrix ans;
        ans.n = n; ans.m = d.m;
        rep(i, 0, ans.n) rep(j, 0, ans.m)
            rep(k, 0, m)
                (ans[i][j] += (ll) a[i][k] * d[k][j] % MOD) %= MOD;
        return ans;
    }
    Matrix operator+ (Matrix d) {
        Matrix ans;
        ans.n = n; ans.m = m;
        rep(i, 0, n) rep(j, 0, m)
            ans[i][j] = (a[i][j] + d[i][j]) % MOD;
        return ans;
    }
} val[N][N], dp[N], MAT;

Matrix qkpow(Matrix a, int k) {
    Matrix ans = a; k--;
    for(; k; k >>= 1, a = a * a)
        if(k & 1) ans = ans * a;
    return ans;
}

void init() {
    MAT.n = MAT.m = 1;
    MAT[1][0] = MAT[1][1] = MAT[0][1] = 1;
}

char s[N];

int main() {
    File(cell);
    init();
    int n;
    scanf("%d%s", &n, s + 1);
    rep(i, 1, n) {
        val[i][i] = qkpow(MAT, s[i] - '0');
        rep(j, i + 1, n) 
            val[i][j] = qkpow(val[i][j - 1], 10) * qkpow(MAT, s[j] - '0');
    }
    rep(i, 1, n) {
        dp[i] = val[1][i];
        rep(j, 1, i - 1) 
            dp[i] = dp[i] + dp[j] * val[j + 1][i];
    }
    printf("%d\n", dp[n][0][0]);
    return 0;
}