2014
03-16

Robot

An intelligent robot decided to learn a new language which has many words. In the i-th day the robot could memorize i^k (the k-th power of i) words. The exception is, on Saturday and Sunday, the robot will do some sports instead of learning the boring language. For example, if the first day is Wednesday and k = 2, the number of words the robot memorized each day is 1, 4, 9, 0, 0, 36, 49…
And n days passed. Do you know how many words the robot has memorized? The answer may be huge, just output the remainder after divided by 1000000007.

The first line contains an integer T (T<=20) indicating the number of test cases.
T*2 lines follows. the first line of each test case contains a string(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday) indicating the first day after the robot decided to learn a new language.
The second line contains two integers n (1<=n<=1000000000) and k (1<=k<=10).

The first line contains an integer T (T<=20) indicating the number of test cases.
T*2 lines follows. the first line of each test case contains a string(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday) indicating the first day after the robot decided to learn a new language.
The second line contains two integers n (1<=n<=1000000000) and k (1<=k<=10).

3
Monday
10 1
Wednesday
7 2
Saturday
3 10

Case 1: 42
Case 2: 99
Case 3: 59049

Wa了好几遍，因为写法写搓了，多判断从周末开始到下周周末的周末的情况（周日算到下周六，多加了个下周六的）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long LL;
const LL mod=1000000007;
LL C[13][13];
int K;
struct Matrix{
LL m[13][13];
}E,D[8],O;
LL Pow(LL a,LL b){
LL ans=1;
while(b){
if(b&1) b--,ans=(ans*a)%mod;
else b/=2,a=(a*a)%mod;
}
return ans;
}
void init(){
for(int i=1;i<=12;i++){
for(int j=1;j<=12;j++)
E.m[i][j]=(i==j);
}
memset(C,0,sizeof(C));
for(int i=1;i<=12;i++){
C[i][0]=C[i][i]=1;
C[i][1]=i;
for(int j=2;j<i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
C[0][0]=1;
for(int i=1;i<=12;i++){
for(int j=0;j<=i;j++)
C[i][j]=(C[i][j]*Pow(7,j))%mod;
}
memset(O.m,0,sizeof(O.m));
for(int i=1;i<=K;i++){
for(int j=i;j<=K;j++){
O.m[i][j]=C[K-i][j-i];
}
}
for(int i=1;i<=7;i++){
//memset(D[i].m,0,sizeof(D[i].m));
D[i].m[K][1]=1;
for(int j=K-1;j>=1;j--)
D[i].m[j][1]=(D[i].m[j+1][1]*i)%mod;
}
}
Matrix Multi(Matrix A,Matrix B){
Matrix ans;
for(int i=1;i<=K;i++){
for(int j=1;j<=K;j++){
ans.m[i][j]=0;
for(int k=1;k<=K;k++)
ans.m[i][j]=(ans.m[i][j]+(A.m[i][k]*B.m[k][j])%mod)%mod;
}
}
return ans;
}
Matrix Pow(Matrix A,LL k){
Matrix ans=E;
while(k){
if(k&1) k--,ans=Multi(ans,A);
else k/=2,A=Multi(A,A);
}
return ans;
}
Matrix ans;
for(int i=1;i<=K;i++){
for(int j=1;j<=K;j++)
ans.m[i][j]=(A.m[i][j]+B.m[i][j])%mod;
}
return ans;
}
Matrix Sum(Matrix A,LL k){
if(k==0) return E;
}
LL get(LL x,LL n){
LL ans=(Multi(Sum(O,n),D[x])).m[1][1]%mod;
return ans;
}
void Print(Matrix A){
for(int i=1;i<=K;i++){
for(int j=1;j<=K;j++)
cout<<A.m[i][j]<<" ";
cout<<endl;
}
}
char s[7][10]={"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int main(){
int T;
scanf("%d",&T);
char str[10];
for(int cas=1;cas<=T;cas++){
scanf("%s",&str);
int st=1;
for(;st<=7;st++){
if(strcmp(s[st-1],str)==0)    break;
}
LL n,k,ans=0;
scanf("%I64d%I64d",&n,&k);
K=k+1;
init();
//Print(O);
int i=st;
int x=0;
for(;i!=st+7;i++){
x++;
if(i==6 || i==7 || i==6+7 || i==7+7) continue;
if( n-x<0) break;
/*cout<<x<<":"<<(n-x)/7<<" "<<endl;
cout<<get(x,(n-x)/7)<<endl;*/
ans=(ans+get(x,(n-x)/7))%mod;
}
//cout<<"Case "<<cas<<": "<<ans<<endl;
printf("Case %d: %I64d\n",cas,ans);
}
return 0;
}

1. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.