bzoj2323 [ZJOI2011]细胞

2018-02-27 08:59:23来源:cnblogs.com作者:hehe_54321人点击

分享

http://www.lydsy.com/JudgeOnline/problem.php?id=2323

根本想不到...

方法:

get(i,j)表示第i到j个数字拼起来组成的数字
ans[i][0/1]表示第一次分裂中,第i个数字之后断开,前i个数字第二次分裂后形成的最后一个二次分裂体否/是与其之后的二次体相切的总方案数
fib[i]表示斐波那契数列的第i项(令fib[0]=1,fib[1]=0)
ans[i][0]=sum{ans[i-j][0]*fib[get(i-j+1,i)]}+sum{ans[i-j][1]*fib[get(i-j+1,i)+1]},1<=j<=i
ans[i][1]=sum{ans[i-j][0]*fib[get(i-j+1,i)+1]}+sum{ans[i-j][1]*fib[get(i-j+1,i)+2]},1<=j<=i

解释:

很容易可以看出,只要第一步、第二步中任何一步有至少一处划分方法不一样,那么就是不同的方案。

(可以说这道题里不用关心去重的问题)

首先确定对于已确定数量(n个)的一些二次分裂体,如何得到其合并方案数f1(n)。

可以得到f1(n)=fib[n],解释

(当然像我这种蒟蒻就只能用n^2的算法打打表找找规律什么的,这个算法就是对于每个n枚举最后一段长度,不过这一步不是题目的重点,找规律也是可以的..吧)

然后确定ans数组的计算方式。(这个ans数组的第二维设计很有意思,根本想不到)

假设现在要求ans[i][1]。那么首先可以枚举从最后切下j个数字,作为一个一次分裂体。这个一次体分裂后形成get(i-j+1,i)个二次体。

那么,由于第二维是1,这些二次体要求与第i个之后的数字形成的第一个二次体相切。

现在,这些二次体与第i-j+1个之前的数字形成的最后一个二次体可能有两种关系:相切或者不相切。

如果相切,那么这一小段的情况总数,相当于get(i-j+1,i)+2个二次体合并的方案数,就是fib[get(i-j+1,i)+2]

(让这一段所含的get(i-j+1,i)个和两端2个合并,则恰好两端一定会都与中间get(i-j+1,i)个相切,因此可以这样算)

而这一段数字的情况与之前段数字的情况都是独立、互不影响的,因此这一种情况产生的贡献是ans[i-j][1]*fib[get(i-j+1,i)+2]

同理,如果不相切,产生的贡献是ans[i-j][0]*fib[get(i-j+1,i)+1]

最终的方案数是以上两种情况产生的方案相加。

同理可得到求ans[i][0]时的转移方程。

注意初值是ans[0][0]=1,ans[0][1]=0

优化:

斐波那契数列的计算可以用矩阵快速幂优化。

当然,如果直接按照这个去打高精+矩阵快速幂只能得到60分

(当然像我一样明明有了优化策略然而复杂度乱来也可以得到60分)

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 typedef long long LL; 6 const LL md=1000000007; 7 LL n,a[100010]; 8 struct Mat 9 {10     LL dat[3][3],x,y;11     Mat(LL x=0,LL y=0):x(x),y(y){memset(dat,0,sizeof(dat));}12     Mat operator*(const Mat& b)13     {14         Mat temp;15         LL i,j,k;16         for(i=1;i<=x;i++)17             for(j=1;j<=b.y;j++)18                 for(k=1;k<=y;k++)19                     temp.dat[i][j]=(dat[i][k]*b.dat[k][j]+temp.dat[i][j])%md;20         temp.x=x;21         temp.y=b.y;22         return temp;23     }24     Mat& operator*=(const Mat& b)25     {26         return (*this)=(*this)*b;27     }28     Mat& operator=(const Mat& b)29     {30         memcpy(dat,b.dat,sizeof(dat));31         x=b.x;y=b.y;32         return *this;33     }34 }o,s,s2;35 Mat px10[1001];36 Mat pow(const Mat& a,LL b)37 {38     Mat ans=o;39     if(b==0)    return ans;40     Mat base=a;41     while(b!=0)42     {43         if(b&1)    ans*=base;44         base*=base;45         b>>=1;46     }47     return ans;48 }49 Mat mulx(LL l,LL r)50 {51     Mat ans=o;52     for(LL i=0;r>=l;r--,i++)53     {54         ans*=pow(px10[i],a[r]);55     }56     return ans;57 }58 LL ans[1010][1010];59 int main()60 {61     LL i,j;Mat tmp;62     o.x=o.y=2;o.dat[1][1]=o.dat[2][2]=1;63     s.x=s.y=2;s.dat[1][2]=s.dat[2][1]=s.dat[2][2]=1;64     s2.x=1;s2.y=2;s2.dat[1][1]=1;65     px10[0]=s;66     for(i=1;i<=1000;i++) px10[i]=pow(px10[i-1],10);67     //ans[i]->fib[i]68     //fib[0]=1,fib[1]=0;69     scanf("%lld",&n);70     for(i=1;i<=n;i++)    scanf("%1lld",&a[i]);71     ans[0][0]=1;72     for(i=1;i<=n;i++)73         for(j=1;j<=i;j++)74         {75             tmp=s2*mulx(i-j+1,i);76             ans[i][0]=(ans[i][0]+ans[i-j][0]*tmp.dat[1][1])%md;77             ans[i][0]=(ans[i][0]+ans[i-j][1]*tmp.dat[1][2])%md;78             ans[i][1]=(ans[i][1]+ans[i-j][0]*tmp.dat[1][2])%md;79             ans[i][1]=(ans[i][1]+ans[i-j][1]*(tmp*s).dat[1][2])%md;80         }81     printf("%lld",ans[n][0]);82     return 0;83 }

可以发现,在斐波那契数列的计算中出现大量形如

s^(一个十进制高精度整数)

=s^(10^0*x[r]+10^1*x[r-1]+...+10^(r-l)*x[l])

的计算(s表示转移矩阵,l、r表示要算第l到r个数字)。

那么可以拆成(s^(10^0))^x[0]*(s^(10^1))^x[1]*...*(s^(10^p))^x[p]。

可以令px10[i]=s^(10^i),并用递推(px10[i]=pow(px10[i-1],10))预处理出来。

然后就可以拆成px10[0]^x[0]*px10[1]^x[1]*...px10[r-l]*x[l]。

对于每一个l和r,这个式子可以在O(n)时间计算完成(矩阵大小是常数,因此矩阵乘法复杂度是常数)。这样也是60分。

令f2(l,r)=px10[0]^x[0]*px10[1]^x[1]*...px10[r-l]*x[l],可以发现存在递推关系:

f2(l,r)=f2(l+1,r)*pow(px10[r-l],a[l])

因此可以一开始预处理出所有f2(l,r),然后需要时直接调用而不是重新计算。这样就得到了复杂度为O(n^2)的算法。

 1 #pragma GCC optimize(3) 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long LL; 7 const LL md=1000000007; 8 LL n,a[1010]; 9 struct Mat10 {11     LL dat[3][3],x,y;12     Mat(LL x=0,LL y=0):x(x),y(y){memset(dat,0,sizeof(dat));}13     Mat operator*(const Mat& b)14     {15         Mat temp;16         LL i,j,k;17         for(i=1;i<=x;i++)18             for(j=1;j<=b.y;j++)19                 for(k=1;k<=y;k++)20                     temp.dat[i][j]=(dat[i][k]*b.dat[k][j]+temp.dat[i][j])%md;21         temp.x=x;22         temp.y=b.y;23         return temp;24     }25     Mat& operator*=(const Mat& b)26     {27         return (*this)=(*this)*b;28     }29     Mat& operator=(const Mat& b)30     {31         memcpy(dat,b.dat,sizeof(dat));32         x=b.x;y=b.y;33         return *this;34     }35 }o,s,s2;36 Mat px10[1001];37 Mat pow(const Mat& a,LL b)38 {39     Mat ans=o;40     if(b==0)    return ans;41     Mat base=a;42     while(b!=0)43     {44         if(b&1)    ans*=base;45         base*=base;46         b>>=1;47     }48     return ans;49 }50 Mat mulx[1010][1010];51 LL ans[1010][1010];52 int main()53 {54     LL i,j,l,r;Mat tmp;55     o.x=o.y=2;o.dat[1][1]=o.dat[2][2]=1;56     s.x=s.y=2;s.dat[1][2]=s.dat[2][1]=s.dat[2][2]=1;57     s2.x=1;s2.y=2;s2.dat[1][1]=1;58     px10[0]=s;59     for(i=1;i<=1000;i++)    px10[i]=pow(px10[i-1],10);60     scanf("%lld",&n);61     for(i=1;i<=n;i++)    scanf("%1lld",&a[i]);62     for(r=1;r<=n;r++)63     {64         mulx[r][r]=pow(px10[0],a[r]);65         for(l=r-1;l>=1;l--)66             mulx[l][r]=mulx[l+1][r]*pow(px10[r-l],a[l]);67     }68     ans[0][0]=1;69     for(i=1;i<=n;i++)70         for(j=1;j<=i;j++)71         {72             tmp=s2*mulx[i-j+1][i];73             ans[i][0]=(ans[i][0]+ans[i-j][0]*tmp.dat[1][1])%md;74             ans[i][0]=(ans[i][0]+ans[i-j][1]*tmp.dat[1][2])%md;75             ans[i][1]=(ans[i][1]+ans[i-j][0]*tmp.dat[1][2])%md;76             ans[i][1]=(ans[i][1]+ans[i-j][1]*(tmp*s).dat[1][2])%md;77         }78     printf("%lld",ans[n][0]);79     return 0;80 }

相关文章

    无相关信息

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台