Description：

给一个数字串，把他划分成 $m$ 个部分，每一个部分看成一个十进制数，再分成这个十进制数这么多部分，再互相合并，要求合并后每一部分都不小于 $2$ ，求总方案数。

$1\leqslant n \leqslant10^3$

## Solution：

首先发现如果最后的序列为 $a_1,a_2,a_3,\dots,a_m$ ，那么这个划分的合并方案数就是 $\begin{align}fib(\sum_{i=1}^m a_i)\end{align}$ ，证明的话，把每个合并的块的第一个看作代表元素，那么就是 $[1,n]$ 的一个不存在相邻元素的子集的方案数，这个的证明大概就是枚举最后一个数在最终被分到了哪里，然后发现这个就是斐波那契数，所以让我们求的实际就是每一种划分方案 $fib(\sum a_i)$ 的和，肯定是 $DP$ ，不妨先思考每一个方案是通过怎样的 $DP$ 路径贡献答案的，肯定是对于每一个 $a_i$ 分一块，那么我们可以设 $f[i]$ 表示到 $i$ 位置时的矩阵，每次转移乘一个矩阵上去，最后得到答案，复杂度 $O(n^2\log n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000000007

int n;

#define MAXN 1010

inline int read()

{

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	return c - '0';

}

int a[MAXN];

struct matrix

{

	int m[3][3];

	matrix(){memset(m,0,sizeof(m));}

	inline void init()

	{

		m[1][1] = 1;m[2][2] = 1;

		return;

	}

	inline void fib_init()

	{

		m[1][1] = 1;m[2][1] = 1;m[1][2] = 1;m[2][2] = 0;

		return;

	}

	inline friend matrix operator * (matrix a,matrix b)

	{

		register matrix c;

		for(register int i = 1;i <= 2;++i)

			for(register int j = 1;j <= 2;++j)

				for(register int k = 1;k <= 2;++k)

					c.m[i][j] = (c.m[i][j] + 1ll * a.m[i][k] * b.m[k][j] % MOD) % MOD;

		return c;

	}

	inline friend matrix operator + (matrix a,matrix b)

	{

		for(register int i = 1;i <= 2;++i)

			for(register int j = 1;j <= 2;++j)

				a.m[i][j] = (a.m[i][j] + b.m[i][j]) % MOD;

		return a;

	}

	inline friend matrix operator ^ (matrix a,int b)

	{

		register matrix res;res = a;--b;

		while(b > 0)

		{

			if(b & 1)res = res * a;

			a = a * a;

			b = b >> 1;

		}

		return res;

	}

}f[MAXN],fib[11];

int main()

{

	scanf("%d",&n);

	for(register int i = 1;i <= n;++i)a[i] = read();

	f[0].init();fib[0].init();fib[1].fib_init();

	for(register int i = 2;i <= 10;++i)fib[i] = fib[i - 1] * fib[1];

	for(register int i = 1;i <= n;++i)

	{

		matrix t = fib[a[i]],tmp;tmp.fib_init();

		for(register int j = i - 1;j >= 0;--j)

		{

			f[i] = f[i] + t * f[j];

			tmp = tmp ^ 10;

			t = t * (tmp ^ a[j]);

		}

	}

	cout << f[n].m[2][2] << endl;

	return 0;

}