题意：给你n和k，求(1^k + 2^k + 3^k + ... + n^k) % 2^32， n <= 1e15, k <= 50
思路：可以知道f(x+1) = f(x) + (x+1)^k,
(x+1)^k 可以用二项式定理展开变成C(k, 0)*x^k+C(k, 1)*x^(k-1)...+C(k, k)*x^0
这就可以构造矩阵快速幂了。
具体思路：
代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; const int maxn = 55; unsigned int c[maxn][maxn]; ll n, K; struct node { unsigned int s[maxn][maxn]; }; node mul(node a, node b) { node t; memset(t.s, 0, sizeof(t.s)); for(int i = 0; i < K+2; i++) for(int k = 0; k < K+2; k++) for(int j = 0; j < K+2; j++) t.s[i][j] = t.s[i][j]+a.s[i][k]*b.s[k][j]; return t; } node mt_pow(node p, ll k) { node q; memset(q.s, 0, sizeof(q.s)); for(int i = 0; i < K+2; i++) q.s[i][i] = 1; while(k) { if(k%2) q = mul(p, q); p = mul(p, p); k /= 2; } return q; } void init() { for(int i = 1; i < maxn; i++) for(int j = 0; j <= i; j++) { if(!j || j==i) c[i][j] = 1; else c[i][j] = c[i-1][j]+c[i-1][j-1]; } } int main(void) { init(); // freopen("out.txt", "w", stdout); int _, ca = 1; cin >> _; while(_--) { scanf("%lld%lld", &n, &K); if(K == 0) printf("Case %d: %u\n", ca++, (unsigned int)n); else { node base; memset(base.s, 0, sizeof(base.s)); base.s[0][0] = 1; for(int i = 1; i < K+2; i++) base.s[0][i] = c[K][i-1]; for(int i = 1; i < K+1; i++) for(int j = i; j < K+2; j++) base.s[i][j] = c[K-i+1][j-i]; base.s[K+1][K+1] = 1; node ans = mt_pow(base, n-1); unsigned int res = 0; for(int i = 0; i < K+2; i++) res += ans.s[0][i]; printf("Case %d: %u\n", ca++, res); } } return 0; }
