思路: 构造矩阵+矩阵快速幂
分析:
1 题目给定n和k要求(1K + 2K + 3K+ ... + NK) % 232
2 具体的思路见下图
3 对于求组合数,我们可以利用公式C(n , k+1) = C(n , k)*(n-k)/(k+1) ,那么我们可以先打表求出50之内的所有的组合数
代码:
/************************************************ * By: chenguolin * * Date: 2013-08-29 * * Address: http://blog.csdn.net/chenguolinblog * ************************************************/ #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long int64; const int64 MOD = (int64)1<<32; const int N = 55; int64 n , k; int64 c[N][N]; struct Matrix{ int64 mat[N][N]; Matrix operator*(const Matrix &m)const{ Matrix tmp; for(int i = 0 ; i < (k+2) ; i++){ for(int j = 0 ; j < (k+2) ; j++){ tmp.mat[i][j] = 0; for(int t = 0 ; t < (k+2) ; t++) tmp.mat[i][j] += mat[i][t]*m.mat[t][j]%MOD; tmp.mat[i][j] %= MOD; } } return tmp; } }; int64 getVal(){ c[0][0] = 1; for(int i = 1 ; i < N ; i++){ c[i][0] = 1; for(int j = 1 ; j <= i ; j++) c[i][j] = c[i][j-1]*(i-j+1)/(j); } } void init(Matrix &m){ memset(m.mat , 0 , sizeof(m.mat)); for(int i = 0 ; i <= k ; i++){ int x = 0; for(int j = i ; j <= k ; j++ , x++) m.mat[i][j] = c[k-i][x]; } for(int i = 0 ; i <= k ; i++) m.mat[k+1][i] = m.mat[0][i]; m.mat[k+1][k+1] = 1; } int64 Pow(Matrix &m){ Matrix ans; memset(ans.mat , 0 , sizeof(ans)); for(int i = 0 ; i <= k+1 ; i++) ans.mat[i][i] = 1; n--; while(n){ if(n%2) ans = ans*m; n /= 2; m = m*m; } int64 sum = 0; for(int i = 0 ; i < k+2 ; i++){ sum += ans.mat[k+1][i]%MOD; sum %= MOD; } return sum; } int main(){ int cas = 1; int Case; Matrix m; getVal(); scanf("%d" , &Case); while(Case--){ scanf("%llu%llu" , &n , &k); init(m); printf("Case %d: " , cas++); printf("%llu\n" , Pow(m)); } return 0; }
时间: 2024-10-25 18:26:33