【题目来源】
https://www.luogu.com.cn/problem/P4541
https://www.acwing.com/problem/content/2299/
https://oj.youdao.com/problem/129
https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P4541
【题目描述】
2222年，人类在银河系外的某颗星球上发现了生命，并且携带了一个细胞回到了地球。经过反复研究，人类已经完全掌握了这类细胞的发展规律：
这种细胞最初的形态是“长条形”，一端是头，一端是尾，中间是躯干。细胞内部含有一列密码（你可以认为它是这种细胞的DNA）。密码是一个长度为n的数字串，且仅含有1~9这9种数字，沿着细胞的躯干从头到尾排列着。
首先，细胞会经历一次分裂。细胞将沿躯干方向分裂成若干个球体，躯干将退化成丝状物，连接着相邻的球体。在分裂过程中，质量是均匀分布的。换句话说，若分裂成k个球体，每个球体的质量为原来的1/k。然而，密码的分布是不确定的。若分割成k个球体，密码会被切割成k段（每段长度至少为1），并按从头到尾的顺序分布在各个球体中。如图，为其中一种合法的一次分裂：
接下来，细胞会经历二次分裂。对于每个球体，其中会含有一小段密码（注意他是有序的），我们把它看作一个十进制的数T。这个球体会被分割成T个小球体，并排成一排，之间用躯干退化成的丝状物相连接，并且质量仍然是均匀分布的，每个小球体的质量都是原球体的1/T。至此，密码已经发挥了它的作用，便消失了。如图，为二次分裂：
最后，细胞会进行变异。相邻小球体之间的丝状物可能会退化掉，这两个小球体便会以相切的方式直接连接。显然，二次分裂后，除两端外的每个小球体都有两段丝状物与其连接（头尾两端的小球体只有一段丝状物与其相连）。对于每个小球体，必须至少退化一段与其相连的丝状物，否则这个结构不稳定，会继续变异。如图，为一种稳定的变异：
现在，我们想知道，对于一个给定密码的细胞，总共有多少种稳定的结构。两种结构被认为相同，当且仅当他们拥有相同个数的小球体，从头到尾每个小球体的质量相同，并且从头到尾每对相邻小球体之间的连接方式相同（都是通过丝状物相连或都是通过相切直接相连）。你只需要回答这个结果 mod 1000000007 即可。
【输入格式】
第一行为一个正整数n，表示细胞密码的长度。
第二行共n个数字，为给定的细胞密码，中间没有空格。
【输出格式】
只包含一个整数，为细胞的种数 mod 1000000007的结果。
【输入输出样例】
| 输入样例1 | 输出样例1 | 输入样例2 | 输出样例2 | 输入样例3 | 输出样例3 |
| 1 1 | 0 | 1 5 | 3 | 2 11 | 56 |
【数据规模】
对于5%的数据满足，n ≤ 6；
对于25%的数据满足，n ≤ 25；
对于60%的数据满足，n ≤ 100；
对于70%的数据满足，n ≤ 300；
对于100%的数据满足，n ≤ 1000。
【算法分析】
● 结构体构造函数：https://blog.csdn.net/hnjzsyjyj/article/details/139553390
● 从下标1处开始输入字符串的一种 C++ 语法：https://blog.csdn.net/hnjzsyjyj/article/details/133217375
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
char str[N];int main() {scanf("%s",str+1); //从s的首地址+1开始输入int len=strlen(str+1);cout<<len<<endl;for(int i=1; i<=len; i++) cout<<str[i]<<" ";return 0;
}/*
in:
abcde
out:
5
a b c d e
*/● 快读函数：https://blog.csdn.net/hnjzsyjyj/article/details/120131534
● 动态规划“最后一步法”：https://blog.csdn.net/hnjzsyjyj/article/details/112797538
【算法代码】
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const LL MOD=1e9+7;
const int maxn=1005;
char s[maxn];
int n;struct Cell {LL c[3][3];Cell() {memset(c,0,sizeof c);}
} a[maxn],f[maxn];Cell mul(Cell a,Cell b) {Cell x;for(int i=1; i<3; i++)for(int j=1; j<3; j++)for(int k=1; k<3; k++)(x.c[i][j]+=(a.c[i][k]*b.c[k][j])%MOD)%=MOD;return x;
}void add(Cell &a,Cell b) {for(int i=1; i<3; i++)for(int j=1; j<3; j++)(a.c[i][j]+=b.c[i][j])%=MOD;
}int main() {scanf("%d%s",&n,s+1);f[0].c[1][1]=2;f[0].c[1][2]=f[0].c[2][1]=-1;f[0].c[2][2]=1;a[0].c[1][2]=a[0].c[2][1]=a[0].c[2][2]=1;for(int i=1; i<=n; i++) {Cell x;a[i]=a[i-1];x=a[i];int t=9;while(t) {if(t & 1) a[i]=mul(a[i],x);x=mul(x,x);t>>=1;}}for(int i=1; i<=n; i++) {Cell x;x.c[1][1]=x.c[2][2]=1;for(int j=i; j>0; j--) {int t=s[j]-'0';while(t--) x=mul(x,a[i-j]);add(f[i],mul(f[j-1],x));}}printf("%lld\n",(f[n].c[2][2]+MOD)%MOD);return 0;
}/*
in:
2
11out:
56
*/
【参考文献】
https://blog.csdn.net/cgh_Andy/article/details/64441453
https://www.cnblogs.com/cghAndy/p/6594538.html
https://www.cnblogs.com/Miracevin/p/9748231.html
https://www.cnblogs.com/AKCqhzdy/p/10280706.html
https://blog.csdn.net/m0_62999279/article/details/124915578
https://vjudge.net/article/2874
https://www.cnblogs.com/Azurestars/p/15491714.html