题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=3369
解题：
设 s(n+1) = s(n) + n^k ; c（k,i） 为二项式系数
只要将 n^k 分解成 (n-1+1)^k ------> n^k = sigma( (n-1)^i*c(k,i) );
然后写成矩阵型式 ：
s(n+1) (n+1)^k ............. n+1 1
s(n) n^k n^(k-1) .... n 1
同理对于（n+7）^ k 也可以写成 (n+7)^k = sigma( (n)^i * c(k,i) * 7^(k-i) )；
不知道标程为什么那么短。。。貌似方法不一样???
code:
#include<iostream>
using namespace std;
typedef long long LL;
const int mod = 1000000007;
struct node {
long long g[15][15];
};
node start;
char st[10][10] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int c[15][15];
LL fac[20];
void init() {
int i,j;
c[0][0] = 1;
for( i = 1,fac[0] = 1 ; i<15; i++ ) {
c[i][0] = 1;
for( j=1; j<=i ;j++) c[i][j] = c[i-1][j-1]+c[i-1][j];
fac[i] = (fac[i-1]*7)%mod;
}
}
inline node multi(node a,node b,int n) {
node ans;
memset(ans.g,0,sizeof(ans.g));
int i,j,k;
for( k = 0 ; k<= n;k++ )
for( i = 0 ; i<=n; i++)
if( a.g[i][k] )
for( j = 0 ; j<= n;j++ ){
ans.g[i][j] = ( ans.g[i][j] + a.g[i][k]*b.g[k][j])%mod;
}
return ans;
}
inline LL sub(int n,int pos,int k) {
LL res = 0;
node ans,t;
int first = 7-pos ,i,j ;
LL tmp = 1ll;
memset(ans.g,0,sizeof(ans.g));
t = ans;
for( i = 0 ;i <= k+1;i++ ) {
for( j = i ; j <= k+1 ;j++ ) {
if( i == 0 && j == 0) t.g[j][i] = 1;
else if( i == 0 && j>0) t.g[j][i] = (fac[j-1]*c[k-i][k-j+1])%mod;
else t.g[j][i] = (fac[j-i]*c[k-i+1][j-i])%mod;
}
}
if( first == 0) first = 7;
for( i = k+1 ; i >0; i-- ) {
ans.g[0][i] = tmp;
tmp = (tmp*first)%mod;
}
ans.g[0][0] = ans.g[0][1];
if( n >= first ) {
int num = (n-first)/7;
node now = ans ,tt = t;
while( num ) {
if(num&1) now = multi(now,tt,k+1);
tt = multi(tt,tt,k+1);
num >>= 1;
}
res += now.g[0][0];
res %= mod;
}
first = 8-pos; tmp = 1ll;
for( i = k+1 ; i > 0; i-- ) {
ans.g[0][i] = tmp;
tmp = (tmp*first)%mod;
}
ans.g[0][0] = ans.g[0][1];
if( n >= first ) {
int num = (n-first)/7;
node now = ans ,tt = t;
while( num ) {
if(num&1) now = multi(now,tt,k+1);
tt = multi(tt,tt,k+1);
num >>= 1;
}
res += now.g[0][0];
res %= mod;
}
return res;
}
inline void solve(int n,int pos,int k) {
node ans,t = start;
int day = n , i ;
memset(ans.g,0,sizeof(ans.g));
for( i = 0 ; i <= k+1; i++ ) {
ans.g[0][i] = 1ll;
}
n--;
while( n ) {
if(n&1) ans = multi(ans,t,k+1);
t = multi(t,t,k+1);
n >>= 1;
}
LL res = ans.g[0][0];
res -= sub(day,pos,k);
cout<<(res%mod+mod)%mod<<endl;
}
int main() {
int test ,tc = 1, n ,k, i ,j;
init();
scanf("%d",&test);
char s[100];
while( test-- ) {
scanf("%s%d%d",s,&n,&k);
int pos ;
for( i = 0;i < 7;i++ )
if( strcmp(s,st[i]) == 0)
break;
pos = i+1;
memset(start.g,0,sizeof(start.g));
start.g[0][0] = 1;
for( i = 0 ;i <= k+1;i++ ) {
for( j = i ; j <= k+1 ;j++ ) {
if( i == 0 ) start.g[j+1][i] = c[k-i][j-i];
else start.g[j][i] = c[k-i+1][j-i];
}
}
printf("Case %d: ",tc++);
solve(n,pos,k);
}
return 0;
}
