首页 > ACM题库 > HDU-杭电 > HDU 3369-Robot-分治-[解题报告]HOJ
2014
03-16

HDU 3369-Robot-分治-[解题报告]HOJ

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

题目:hdu 3369 Robot

题意:告诉你从周几开始,到第n天总的学会单词的个数,其中第i天学会i^k个单词,周末学会单词为0

思路:给的k的范围比较小,n的范围比较大

开始想的是,枚举k,但是这样对于n并没有影响

所以,我们要处理的应该是,i^k+(i+7)^k+(i+14)^k+….(i+7*j)^k这样的一个通式

由于k的范围比较小,展开成k+1项二项式表示之后可以构造矩阵,然后转化成二分求矩阵和

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 Add(Matrix A,Matrix B){
    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;
    if(k==1) return Add(A,E);
    if(k&1) return Multi(Sum(A,k/2),Add(E,Pow(A,(k+1)/2)));
    else return Add(Multi(Sum(A,(k-1)/2),Add(E,Pow(A,k/2))),Pow(A,k));
}
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;
}

参考:http://blog.csdn.net/shiyuankongbu/article/details/17302603


  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();}.