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
图源：点击打开链接
矩阵快速幂，D^(x - 1) * f(1) = f(x)
C(m,n)用杨辉三角的对应关系求得较为简单易得
D * f(x) = f(x + 1)
AC代码：
#include<algorithm> #include<iostream> #include<cstring> #include<stdio.h> #include<cmath> using namespace std; #define ll long long const ll mod = ((ll) 1 << 32); struct jz { ll m[55][55]; }f, d; ll N, K; ll C[55][55]; void yh() //利用杨辉三角值求C(m,n) { for(int i = 0; i <= 50; i++) { C[i][0] = 1; C[i][i] = 1; C[i][1] = i; } for(int i = 2; i <= 50; i++) { for(int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } } jz mul(jz A, jz B)//A*B { jz c; for(int i = 1; i <= K + 2; i++) { for(int k = 1; k <= K + 2; k++) { c.m[i][k] = 0; for(int j = 1; j <= K + 2; j++) c.m[i][k] = (c.m[i][k] + A.m[i][j] * B.m[j][k]) % mod; } } return c; } jz pow_(jz A, ll n) //A^n { jz ans = f; while(n) { if(n & 1) { n--; ans = mul(ans, A); } else { n /= 2; A = mul(A, A); } } return ans; } void D() { for(int i = 1; i <= K + 2; i++) { for(int j = 1; j <= K + 2; j++) { d.m[i][j] = 0; } } d.m[1][1] = 1; for(int i = 2; i <= K + 2; i++) d.m[1][i] = C[K][i - 2]; for(int i = 2; i <= K + 2; i++) { for(int j = i; j <= K + 2; j++) { d.m[i][j] = C[K - i + 2][j - i]; } } } void F() //f(1) { for(int i = 1; i <= K + 2; i++) { f.m[i][1] = 1; } } int main() { int T; cin>>T; yh(); for(int j = 1; j <= T; j++) { cin>>N>>K; F(); D(); jz flag = pow_(d, N - 1); jz ans = mul(flag, f); printf("Case %d: %lld\n", j, ans.m[1][1]); } return 0; }
