http://acm.hdu.edu.cn/showproblem.php?pid=1757
A Simple Math Problem
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5829 Accepted Submission(s): 3555
Problem Description
Lele now is thinking about a simple function f(x).
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .
Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
Input
The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
Output
For each case, output f(k) % m in one line.
Sample Input
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
Sample Output
45 104
题目分析：看到 1）f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);【一个递推式】
2） k<2*10^9 , m < 10^5【数据超大】
就知道是矩阵快速幂了【好吧..我之前并不知道..qaq..】
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,k;
void mul(long long wqw[],long long tat[][])
{
long long or2[];
// cout <<
memset(or2,,sizeof(or2));
for(int i = ; i < ; i++)
{
for(int j = ; j < ; j++)
{
or2[i]+=(wqw[j]*(tat[j][i]))%k;
or2[i]%=k;
}
}
memcpy(wqw,or2,sizeof(or2));
}
void mulself(long long awa[][])
{
long long or3[][];
memset(or3,,sizeof(or3));
for(int i = ; i < ; i++)
{
for(int j = ; j< ; j++)
{
for(int kk = ; kk < ; kk++)
{
or3[i][j]+=((awa[i][kk])%k)*((awa[kk][j])%k)%k;
or3[i][j]%=k;
}
}
}
memcpy(awa,or3,sizeof(or3));
}
int main()
{
while(scanf("%lld%lld",&n,&k)==)
{ long long qaq[][];
long long qwq[];
long long orz[]={,,,,,,,,,};
memset(qaq,,sizeof(qaq));
for(int i = ; i < ; i++)
{
scanf("%lld",&qaq[i][]);
}
for(int i = ; i < ; i++)
{
qaq[i-][i]=;
}
if(n<)
{
printf("%lld\n",n%k);
}
else
{
n=n-;
while(n)
{
if(n&)mul(orz,qaq);
mulself(qaq);
n/=;
}
cout <<orz[]%k<<endl;
}
}
return ;
}