【题目来源】
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