首页 > ACM题库 > HDU-杭电 > HDU 4471-Homework-快速幂-[解题报告]HOJ
2015
07-16

HDU 4471-Homework-快速幂-[解题报告]HOJ

Homework

问题描述 :

GS is suffering from tons of boring math assignment. He find it make him tired and impatient so he asks you to finish his assignment in hope that he could hang out in many places of interest and enjoy his life.
In this assignment, you’re asked to solve the following problem:
Given a recurrent function
Blackjack

and boundary values
Blackjack

You should solve for f[n].
What a easy problems! Wait for a moment, you see a few lines in the last paragraph. It reads as follows: To make the problem a little hard, you are now informed that, at some special values of n (there are q such values, namely n1, n2, . . . , nq), the recurrent formula changes into something else, which means for the kth such value nk, the recurrent formula changes into
Blackjack

Still an easy problem, isn’t it?
Since f[n] may be quite large, you just need to output f[n] module 109 + 7.

输入:

There are several test cases.
For each test case, the first line contains three integers n (m < n ≤ 109), m (1 ≤ m ≤ 100), q (0 ≤ q ≤ 100). The second line contains m integers, namely f[1], f[2], . . . , f[m].
The following line contains several integers, first comes t (t ≤ 100), then t integers namely c[1], c[2], . . . , c[t].
The following q lines describe q special cases of the recurrent formula, each containing several integers, namely nk, tk (tk ≤ 100, tk < nk), ck[1], ck[2], . . . , ck[tk], as mentioned earlier. It is satisfied that ni != nj if i != j.
All integers are non-negative. Unless specified, all integers are not greater than 109.
Input is terminated by EOF.
You might assume that all given data is correct.

输出:

There are several test cases.
For each test case, the first line contains three integers n (m < n ≤ 109), m (1 ≤ m ≤ 100), q (0 ≤ q ≤ 100). The second line contains m integers, namely f[1], f[2], . . . , f[m].
The following line contains several integers, first comes t (t ≤ 100), then t integers namely c[1], c[2], . . . , c[t].
The following q lines describe q special cases of the recurrent formula, each containing several integers, namely nk, tk (tk ≤ 100, tk < nk), ck[1], ck[2], . . . , ck[tk], as mentioned earlier. It is satisfied that ni != nj if i != j.
All integers are non-negative. Unless specified, all integers are not greater than 109.
Input is terminated by EOF.
You might assume that all given data is correct.

样例输入:

7 5 0
1 1 2 3 5
2 1 1
10 5 1
1 1 2 3 5
2 1 1
10 2 1 2

样例输出:

Case 1: 13
Case 2: 76
Hint
In the first sample, you are to solve for f[7] where f[n] = f[n−1]+f[n−2] and f[1] = 1, f[2] = 1, f[3] = 2, f[4] = 3, f[5] = 5. In the second example, you are to solve for f[10] where f[n] = f[n − 1] + f[n − 2] and f[1] = 1, f[2] = 1, f[3] = 2, f[4] = 3, f[5] = 5, as well as specially f[10] = f[9] + 2*f[8].

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=4471

解题思路,矩阵快速幂····特殊点特殊处理·····

令h为计算某个数最多须知前h个数,于是写出方程:

D =

c1 c2 “` c[h-1] c[h]
1 0 “` 0 0
0 1 “` 0 0
0 0   0 0
0 0   1 0

V[x] =

f[x]
f[x-1]
`
`
f[x-h+1]

显然有V[x+1] = D*V[x].D是由系数行向量,一个(h-1)*(h-1)的单位矩阵,和一个(h-1)*1的0矩阵组成。V[x]是一个h行,1列的矩阵。

初始条件为V[m] = (f[m],f[m-1],““`).如果m>h,那么多余的部分不会用到,如果m<h剩下的部分用0取代,相当于人为的添加前项f[0] = 0,f[-1] = 0·····这不会影响结果,而且式子仍然成立。由此计算出V[n],答案就为V[1][1].

其余看一下代码就OK了,还有别人的解题报告,也可以看一下:

链接:

http://www.07net01.com/program/547544.html

我的代码:

 #include<cstdio>
 #include<algorithm>
 using namespace std;
 const int N =102;
 const int mod = 1000000007;
 int h;//计算f[x]时最多和前面h个数有关
 struct matrix
 {
     int row,col;
     int m[N][N];
     void init(int row,int col)
     {
         this->row = row;
         this->col = col;
         for(int i=0; i<=row; ++i)
             for(int j=0; j<=col; ++j)
                 m[i][j] = 0;
     }
 } A,pm[33],ans;
 
 matrix operator*(const matrix & a,const matrix& b)
 {
     matrix res;
     res.init(a.row,b.col);
     for(int k=1; k<=a.col; ++k)
     {
         for(int i=1; i<= res.row; ++i)
         {
             if(a.m[i][k] == 0 ) continue;
             for(int j = 1; j<=res.col; ++j)
             {
                 if(b.m[k][j] == 0 ) continue;
                 res.m[i][j] = (1LL *a.m[i][k]*b.m[k][j] + res.m[i][j])%mod;
             }
         }
     }
     return res;
 }
 
 void cal(int x)
 {
     for(int i=0; i<=31; ++i)
         if(x & (1<<i) ) ans = pm[i]*ans;
 }
 void getPm()
 {
     pm[0] = A;
     for(int i=1; i<=31; ++i)
         pm[i] = pm[i-1]*pm[i-1];
 }
 struct sp//特殊点
 {
     int nk,tk;//nk为点的位置,tk为计算nk时和前面tk个数有关
     int ck[N];
     bool operator<(const sp & o)const//按照nk排序
     {
         return nk<o.nk;
     }
 } p[N];
 int main()
 {
 //    freopen("in.txt","r",stdin);
     int n,m,q,t,f[N],c[N],kase=0;
     while(~scanf("%d%d%d",&n,&m,&q))
     {
         for(int i=m; i>0; --i)   scanf("%d",&f[i]);
         scanf("%d",&t);
         h =t;
         for(int i=1; i<=t; ++i)  scanf("%d",&c[i]);
         for(int i=0; i<q; ++i)
         {
             scanf("%d%d",&p[i].nk,&p[i].tk);
             if(p[i].tk > h) h = p[i].tk;
             for(int j=1; j<=p[i].tk; ++j) scanf("%d",&p[i].ck[j]);
         }
         sort(p,p+q);
         A.init(h,h);
         for(int i=1; i<=t; ++i) A.m[1][i] = c[i];
         for(int i=2; i<=h; ++i)  A.m[i][i-1] = 1;
         getPm();
         ans.init(h,1);
         for(int i = m; i > 0; --i)   ans.m[i][1] = f[i];
         int last=m;
         for(int i=0; i<q; ++i)
         {
             if( p[i].nk <=last ||  p[i].nk >n ) continue;
             cal( p[i].nk-last-1);
             last =  p[i].nk;
             for(int j=1; j<=p[i].tk; ++j)  A.m[1][j] = p[i].ck[j];
             for(int j=p[i].tk+1; j<=h; ++j) A.m[1][j] = 0;
             ans  =A*ans;
         }
         cal(n-last);
         printf("Case %d: %d\n",++kase,ans.m[1][1]);
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/allh123/p/3296276.html