So Easy!
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1729 Accepted Submission(s): 556
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 2013 2 3 2 2013 2 2 1 2013
Sample Output
4 14 4
Source
此题的思路在于这儿....看图...
/*快速矩@ coder Gxjun*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
__int64 ma[][]; //matrix
__int64 ans[][];
void init(__int64 a[][])
{
int i;
for(i=;i<;i++)
a[i][i]=; //E 设置为1
a[][]=;
a[][]=;
}
int main()
{
int a,b,m,n,i,j,k;
__int64 temp[] ;
__int64 hop[][];
while(scanf("%d%d%d%d",&a,&b,&n,&m)!=EOF)
{
if(n==)
{
printf("%I64d\n",(*a)%m);
continue;
}
else if(n==)
{
printf("%I64d\n",(*(a*a+b))%m);
continue;
}
n-=;
init(ans);
/*init(ma);*/
ma[][]=(*a)%m;
ma[][]=(b-a*a)%m;
ma[][]=;
ma[][]=;
while(n>)
{
if(n&)
{
for(k=;k<;k++)
{
memset(temp,,sizeof(temp));
for(i=;i<;i++)
{
for(j=;j<;j++)
{
temp[i]+=ans[k][j]*ma[j][i];
temp[i]%=m;
}
}
ans[k][]=temp[];
ans[k][]=temp[];
}
n--;
continue;
}
memset(hop,,sizeof(hop));
for(k=;k<;k++)
{
for(i=;i<;i++)
{
for(j=;j<;j++)
{
hop[k][i]+=ma[k][j]*ma[j][i];
hop[k][i]%=m;
}
}
}
for(i=;i<;i++)
{
for(j=;j<;j++)
{
ma[i][j]=hop[i][j];
}
}
n>>=;
}
__int64 gong=(*((ans[][]*a)%m+(ans[][]*(a*a+b)%m)%m)%m)%m;
if(gong<) gong=m+gong;
printf("%I64d\n",gong);
}
return ;
}