233 Matrix（矩阵快速幂）
In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 … in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333… (it means a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333…) Besides, in 233 matrix, we got a i,j = a i-1,j +a i,j-1( i,j ≠ 0). Now you have known a 1,0,a 2,0,…,a n,0, could you tell me a n,m in the 233 matrix?
Input
There are multiple test cases. Please process till EOF.
For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 10 9). The second line contains n integers, a 1,0,a 2,0,…,a n,0(0 ≤ a i,0 < 2 31).
Output
For each case, output a n,m mod 10000007.
Sample Input
1 1
1
2 2
0 0
3 7
23 47 16
Sample Output
234
2799
72937
Hint
思路：
题目告诉 a[i][j]=a[i-1][j]+a[i][j-1] 的关系，然后计算出矩阵，带入板子。
完整代码：
#include
#include
using namespace std;
typedef long long ll;
const ll MOD=10000007;
#define mod(x) ((x)%MOD)
#define maxn 15
ll n,nn;
struct mat //矩阵
{
ll m[maxn][maxn];
mat()
{
memset(m,0,sizeof(m)); //记得清空
}
};
//矩阵乘法
mat mat_mul(mat b,mat a) //要是左乘我之前错了好几次
{
mat ret;
for(int i=1;i<=n+2;i++)
{
for(int j=1;j<=n+2;j++)
{
for(int k=1;k<=n+2;k++)
{
ret.m[i][j]=mod(ret.m[i][j]+b.m[i][k]*a.m[k][j]);
}
}
}
return ret;
}
//矩阵快速幂
mat pow_mat(mat a,ll x)
{
mat ret;
for(int i=1;i>=1;
}
return ret;
}
/**
板子和其他的都相似就是左乘不一样
*/
int main()
{
while(cin>>n>>nn)
{
mat a,b;
a.m[1][1]=23;
for(int i=1;i>a.m[i+1][1];
}
a.m[n+2][1]=3;
for(int i=1;i<=n+1;i++)
{
b.m[i][1]=10;
}
for(int i=1;i<=n+2;i++)
{
b.m[i][n+2]=1;
}
for(int i=1;i<n+2;i++)
{
for(int j=2;j<=i;j++)
{
b.m[i][j]=1;
}
}
b=pow_mat(b,nn);
a=mat_mul(b,a);
cout<<a.m[n+1][1]<<endl;
}
return 0;
}
作者：Water_Coder
