为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 268876
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

http://acm.pku.edu.cn/JudgeOnline/problem?id=2440
这是一个递推的题目,公式的推导过程如下:
合法的情况:
000     001     010     011     100     110
设达到长度n-1的时候,得到的分别以上述串结尾的序列个数分别为
f1(n-1) f2(n-1) f3(n-1) f4(n-1) f5(n-1) f6(n-1)
则总共的序列个数F(n-1)=f1(n-1)+f2(n-1)+f3(n-1)+f4(n-1)+f5(n-1)+f6(n-1)
则:
f1(n)=f1(n-1)+f5(n-1)
f2(n)=f1(n-1)+f5(n-1)
f3(n)=f2(n-1)
f4(n)=f2(n-1)
f5(n)=f3(n-1)+f6(n-1)
f6(n)=f4(n-1)
F(n)=f1(n)+f2(n)+f3(n)+f4(n)+f5(n)+f6(n)
    =f1(n-1)+f5(n-1)+f1(n-1)+f5(n-1)+f2(n-1)+f2(n-1)+f3(n-1)+f6(n-1)+f4(n-1)
    =F(n-1)+f1(n-1)+f2(n-1)+f5(n-1)
    =F(n-1)+f1(n-2)+f5(n-2)+f1(n-2)+f5(n-2)+f3(n-2)+f6(n-2)
    =F(n-1)+2*f1(n-2)+2*f5(n-2)+f3(n-2)+f6(n-2)
    =F(n-1)+2*f1(n-3)+2*f5(n-3)+2*f3(n-3)+2*f6(n-3)+f2(n-3)+f4(n-3)
    =F(n-1)+F(n-3)+f1(n-3)+f3(n-3)+f5(n-3)+f6(n-3)
    =F(n-1)+F(n-3)+f1(n-4)+f5(n-4)+f2(n-4)+f3(n-4)+f6(n-4)+f4(n-4)
    =F(n-1)+F(n-3)+F(n-4)

由于是求对2005的模,因此很容易想到肯定有循环出现。经计算循环是200。但是,我下面用矩阵求解。

根据递推式构造矩阵的方法是:
设递推式是:f(n)  =a1*f(n-1)+a2*f(n-2)+a3*f(n-3)
            又有:f(n-1)=    f(n-1)
                和:f(n-2)=                     f(n-2)

 然后就有

                    f(n)         a1   a2   a3     f(n-1)
                   f(n-1)       1    0    0        f(n-2)
                    f(n-2)      0    1    0        f(n-3)

因此矩阵就是 a1 a2  a3
                          1    0   0
                          0    1   0

对于该题而言,矩阵A是  1   0   1   1
                                          1   0   0   0
                                          0   0   0   0
                                          0   1   0   0
                                          0   0   1   0
F(n)=A*F(n-1)
#include<iostream>
#include
<algorithm>
#include
<string>
#include
<vector>
#include
<cmath>
#include
<map>
using namespace std;
void copy(int sor[][4],int des[][4])
{
    
for(int i=0;i<4;i++)
        
for(int j=0;j<4;j++)
            des[i][j]
=sor[i][j];
}

void mul(int sor1[][4],int sor2[][4],int des[][4])
{
    
for(int i=0;i<4;i++)
        
for(int j=0;j<4;j++)
        
{
            des[i][j]
=0;
            
for(int k=0;k<4;k++)
            
{
                des[i][j]
=(des[i][j]+sor1[i][k]*sor2[k][j])%2005;
            }

        }

}

void multiply(int mat[][4],int l,int res[][4])
{
    
if(l<=0)
    
{
        
for(int i=0;i<4;i++)
        
{
            
for(int j=0;j<4;j++)
                res[i][j]
=0;
            res[i][i]
=1;
        }

    }

    
else if(l==1)
    
{
        copy(mat,res);
    }

    
else
    
{
        
int tmp[4][4];
        multiply(mat,l
/2,res);
        mul(res,res,tmp);
        
if(l%2)
            mul(tmp,mat,res); 
// res = tmp * mat
        else copy(tmp,res); //tmp copy-> res;
    }

}

void multiply2(int res[][4],int b[],int ans[])
{
    
for(int i=0;i<4;i++)
    
{
        ans[i]
=0;
        
for(int j=0;j<4;j++)
            ans[i]
=(ans[i]+res[i][j]*b[j])%2005;
    }

}

int solve(int l)
{
    
int f[]={1,2,4,6};
    
if(l<4)
        
return f[l];
    
int mat[4][4]={{1,0,1,1},{1,0,0,0},{0,1,0,0},{0,0,1,0}};
    
int b[]={6,4,2,1};
    
int res[4][4],ans[4];
    multiply(mat,l
-3,res); //res = mat^l
    multiply2(res,b,ans); // ans=res*b
    return ans[0];
}

int main()
{
    
int l;
    
while(scanf("%d",&l)!=EOF)
    
{
        printf(
"%d\n",solve(l));
    }

}
posted on 2009-08-17 20:47 baby-fly 阅读(229) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理