2017-07-11 13:52:23         来源：lifelikes的博客

Given N and K, you have to find

(1K + 2K + 3K + … + NK) % 232
Input

``````Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains two integers N (1 ≤ N ≤ 1015) and K (0 ≤ K ≤ 50) in a single line.
``````

`Output`

``````For each case, print the case number and the result.
``````

`Sample Input`

``````3

3 1

4 2

3 3
``````

`Sample Output`

``````Case 1: 6

Case 2: 30

Case 3: 36
``````

`第一道矩阵快速幂的题目，写了很久。。。 主要是单位矩阵初始化的问题让我很蛋疼。。。`

`写完之后非常激动，想写一波题解，结果发现数学符号根本不会打。。。。尴尬。`

`贴上代码 以示纪念`

``````#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const long long MAX=(long long)1<<32;
class mat
{
public:
int sz;
long long m[55][55];
mat(int sz){
memset(m,0,sizeof m);
this->sz=sz;
}
mat(){memset(m,0,sizeof m);}
mat operator * (mat a)
{
mat cnt(sz);
for(int i=1;i<=sz;i++)
{
for(int j=1;j<=sz;j++)
{
for(int k=1;k<=sz;k++)
cnt.m[i][j]+=(m[i][k]*a.m[k][j])%MAX;
}
}
return cnt;
}
};
mat E;
void init(int sz)
{
memset(E.m,0,sizeof E.m);
E.sz=sz+2;
for(int i=0;i<=55;i++)
{
E.m[i][sz+2]=1;
E.m[i][i]=1;
}
for(int i=sz;i>=2;i--)
{
for(int j=sz+2;j>=i;j--)
{
E.m[i][j]=E.m[i+1][j+1]+E.m[i+1][j];
/*for(int i=1;i<=5;i++)
{
for(int j=1;j<=5;j++)
cout<>=1;
}
/*for(int i=1;i<=5;i++)
{
for(int j=1;j<=5;j++)
cout<

``````