首页 > 代码库 > 2013长沙邀请赛A So Easy!(矩阵快速幂，共轭)
2013长沙邀请赛A So Easy!(矩阵快速幂，共轭)
So Easy!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2286 Accepted Submission(s): 710
Problem Description
A sequence Sn is defined as:
Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn.
You, a top coder, say: So easy!
Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn.
You, a top coder, say: So easy!
Input
There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 215, (a-1)2< b < a2, 0 < b, n < 231.The input will finish with the end of file.
Output
For each the case, output an integer Sn.
Sample Input
2 3 1 20132 3 2 20132 2 1 2013
Sample Output
4144
挑战程序设计竞赛P268，关键是求初始矩阵：
an+1 = a*an+b*bn;
bn+1 = an+a*bn;
a[0][0],a[0][1]分别是公式1里面的系数，a和b;
a[1][0],a[1][1]分别是公式2里面的系数，1和a;
然后就是矩阵快速幂了：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<algorithm> 6 #include<cmath> 7 #define M(a,b) memset(a,b,sizeof(a)) 8 typedef long long LL; 9 10 using namespace std;11 12 13 long long a,b,n,m;14 15 struct matrix16 {17 LL mat[2][2];18 void init()19 {20 mat[0][0] = a;21 mat[0][1] = b;22 mat[1][0] = 1;23 mat[1][1] = a;24 }25 };26 27 matrix mamul(matrix aa,matrix bb)28 {29 matrix c;30 for(int i = 0;i<2;i++)31 {32 for(int j = 0;j<2;j++)33 {34 c.mat[i][j] = 0;35 for(int k = 0;k<2;k++)36 c.mat[i][j]+=(aa.mat[i][k]*bb.mat[k][j]);37 c.mat[i][j]%=m;38 }39 }40 return c;41 }42 43 matrix mul(matrix s, int k)44 {45 matrix ans;46 ans.init();47 while(k>=1)48 {49 if(k&1)50 ans = mamul(ans,s);51 k = k>>1;52 s = mamul(s,s);53 }54 return ans;55 }56 57 int main()58 {59 while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&m)==4)60 {61 matrix ans;62 ans.init();63 ans = mul(ans,n-1);64 printf("%I64d\n",(ans.mat[0][0]*2+m)%m);65 }66 return 0;67 }
2013长沙邀请赛A So Easy!(矩阵快速幂，共轭)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。