2323: [ZJOI2011]细胞
Description
2222年，人类在银河系外的某颗星球上发现了生命，并且携带了一个细胞回到了地球。经过反复研究，人类已经完全掌握了这类细胞的发展规律：
这种细胞最初的形态是“长条形”，一端是头，一端是尾，中间是躯干。细胞内部含有一列密码（你可以认为它是这种细胞的DNA）。密码是一个长度为n的数字串，且仅含有1~9这9种数字，沿着细胞的躯干从头到尾排列着。
首先，细胞会经历一次分裂。细胞将沿躯干方向分裂成若干个球体，躯干将退化成丝状物，连接着相邻的球体。在分裂过程中，质量是均匀分布的。换句话说，若分裂成k个球体，每个球体的质量为原来的1/k。然而，密码的分布是不确定的。若分割成k个球体，密码会被切割成k段（每段长度至少为1），并按从头到尾的顺序分布在各个球体中。如图，为其中一种合法的一次分裂：
接下来，细胞会经历二次分裂。对于每个球体，其中会含有一小段密码（注意他是有序的），我们把它看作一个十进制的数T。这个球体会被分割成T个小球体，并排成一排，之间用躯干退化成的丝状物相连接，并且质量仍然是均匀分布的，每个小球体的质量都是原球体的1/T。至此，密码已经发挥了它的作用，便消失了。如图，为二次分裂：
最后，细胞会进行变异。相邻小球体之间的丝状物可能会退化掉，这两个小球体便会以相切的方式直接连接。显然，二次分裂后，除两端外的每个小球体都有两段丝状物与其连接（头尾两端的小球体只有一段丝状物与其相连）。对于每个小球体，必须至少退化一段与其相连的丝状物，否则这个结构不稳定，会继续变异。如图，为一种稳定的变异：
现在，我们想知道，对于一个给定密码的细胞，总共有多少种稳定的结构。两种结构被认为相同，当且仅当他们拥有相同个数的小球体，从头到尾每个小球体的质量相同，并且从头到尾每对相邻小球体之间的连接方式相同（都是通过丝状物相连或都是通过相切直接相连）。你只需要回答这个结果 mod 1000000007即可。
Input
第一行为一个正整数n，表示细胞密码的长度。
第二行共n个数字，为给定的细胞密码，中间没有空格。
Output
只包含一个整数，为细胞的种数 mod 1000000007的结果。
Sample Input
【样例输入一】1
1
【样例输入二】
1
5
【样例输入三】
2
11
Sample Output
【样例输出一】0
【样例输出二】
3
【样例输出三】
56
HINT
【数据规模】
对于5%的数据满足，n ≤ 6；
对于25%的数据满足，n ≤ 25；
对于60%的数据满足，n ≤ 100；
对于70%的数据满足，n ≤ 300；
对于100%的数据满足，n ≤ 1 000。
Source
【分析】
好题？
感谢数学试卷让我发现了这个可爱的斐波那契数列。。【hhh
然后【矩阵的指数不能mod phi[p]? 。。被奥爷爷d了。。。。
首先，第一步或第三步不同，则出来的结果一定不同【自己想为什么吧、、我就是这样觉得的
对于第三步，他说一个球两边一定有一边被缩了，其实就是n条边，让你选若干条不缩的边，他们不相邻（因为两端的点是有一条边，所以两端的边是不能选的）
这个模型就是数学试卷上的经典模型？f[n]=f[n-1]+f[n-2]，就是枚举第n个选还是不选，就是斐波那契数列。
第三步的判断就搞定了。
对于第一第二步，就是把这个大数字分成很多部分，套上第三步的方案加入答案中，这个可以用DP处理。
f[x][0]表示x前面那条边没有选，
f[x][1]表示x前面那条边选了。
f[i][0]=f[i][0]+f[j][0]*F[nw-3]+f[j][1]*F[nw-2]
f[i][1]=f[i][1]+f[j][0]*F[nw-2]+f[j][1]*F[nw-1]
//F表示斐波那契数列， nw表示j+1~i表示的数。
然后问题来了，F[nw???]怎么求，nw是个极大的数额。。
【一开始我以为矩阵幂的指数可以mod phi 还乐呵呵地打了。。。
其实可以预处理，但是传统的快速幂的话，貌似，挺慢？？而且你要高精？？
传统的快速幂是以2为底的快速幂，他给你的高精数是10进制下的，不如把快速幂改成10为底的，那么你可以发现，有些过程可以合并，比如你算[l,r]的f，中间已经算了[l,r-1]的部分。
所以预处理就是O（n^2*一个不知道多大的常数）
好像别人打的都挺快的。。。可以看看其他解法：http://www.cnblogs.com/cghAndy/p/6594538.html
总时间复杂度：O（n^2*一个不知道多大的常数）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define Mod 1000000007
#define Maxn 1010 int n; struct node
{
LL w[][];
}t[],tt[]; LL a[Maxn],f[Maxn][];
char s[Maxn]; void mul(int z,int x,int y)
{
t[]=tt[];
for(int k=;k<=;k++)
for(int i=;i<=;i++)
for(int j=;j<=;j++)
t[].w[i][j]=(t[].w[i][j]+t[x].w[i][k]*t[y].w[k][j])%Mod;
t[z]=t[];
} void qpow(int x,int b)
{
t[]=tt[];
while(b)
{
if(b&) mul(,x,);
mul(x,x,x);
b>>=;
}
t[x]=t[];
} LL B[Maxn][Maxn][]; LL get_f(int x)
{
t[]=tt[];
t[]=tt[];
for(int i=x;i<=n;i++)
{
qpow(,);
t[]=t[];
qpow(,a[i]);
// mul(4,a[i]-10,4); t[]=t[];
B[x][i][]=t[].w[][];
mul(,,);
B[x][i][]=t[].w[][];
mul(,,);
B[x][i][]=t[].w[][];
}
} void init()
{
tt[].w[][]=;tt[].w[][]=;
tt[].w[][]=;tt[].w[][]=; tt[].w[][]=;tt[].w[][]=;
tt[].w[][]=;tt[].w[][]=; tt[].w[][]=;tt[].w[][]=;
tt[].w[][]=;tt[].w[][]=; t[]=tt[];t[]=tt[];
for(int i=;i<=;i++)
{
mul(i,i-,);
}
} int main()
{
init();
scanf("%d",&n);
scanf("%s",s+);
for(int i=;i<=n;i++) a[i]=s[i]-''; memset(f,,sizeof(f));
f[][]=; int i,j,k;
for(i=;i<=n;i++) get_f(i); for(i=;i<=n;i++)
for(j=;j<i;j++)
{
f[i][]=f[i][]+f[j][]*B[j+][i][];f[i][]%=Mod;
f[i][]=f[i][]+f[j][]*B[j+][i][];f[i][]%=Mod;
f[i][]=f[i][]+f[j][]*B[j+][i][];f[i][]%=Mod;
f[i][]=f[i][]+f[j][]*B[j+][i][];f[i][]%=Mod; }
printf("%d\n",f[n][]);
return ;
}
2017-03-21 21:16:25