HDU 3369 Robot

/*
*  [题意]
*   给出第一天是星期几，给出n，k
*   第i天记忆的单词数是(i^k)，其中特殊地：星期六、日记忆的单词数为0
*   问这n天一共记忆了多少个单词？
*  [解题方法]
*   1、先说怎么求f[n][k] = (1^k)+(2^k)+(3^k)+...+(n^k)
*       原式 = (0+1)^k + (1+1)^k + (2+1)^k +...+ ((n-1)+1)^k
*       设：C(i,j)为组合数，i种元素取j种的方法数
*       由二次多项式得：
*           ((n-1)+1)^k = C(k,0) + C(k,1)*(n-1) +...+ C(k,k)*((n-1)^k)
*           ((n-2)+1)^k = C(k,0) + C(k,1)*(n-2) +...+ C(k,k)*((n-2)^k)
*           ((n-3)+1)^k = C(k,0) + C(k,1)*(n-3) +...+ C(k,k)*((n-3)^k)
*                 ...           ...              ...
*           (1+1)^k = C(k,0) + C(k,1)*1     +...+ C(k,k)*1
*           (0+1)^k = C(k,0)
*       所以得递推式：
*           f[n][k] = C(k,0)*f[n-1][0] + C(k,1)*f[n-1][1] +...+ C(k,k)*f[n-1][k] + 1
*       { 注：+1是因为最后一个式子"(0+1)^k = C(k,0)" }
*       所以得矩阵：
*           |C(0,0) 0....................0 1|     |f[n-1][0]|     |f[n][0]|
*           |C(1,0) C(1,1) 0.............0 1|     |f[n-1][1]|     |f[n][1]|
*           |...............................|     |.........|     |.......|
*           |C(j,0) C(j,1)...C(j,j) 0....0 1|  *  |f[n-1][j]|  =  |f[n][j]|
*           |...............................|     |.........|     |.......|
*           |C(k,1) C(k,2) C(k,3)...C(k,k) 1|     |f[n-1][k]|     |f[n][k]|
*           |0...........................0 1|     |1        |     |1      |
*   2、分别求星期六、日的总值，用上面所求到的值减去这两个本不应该算的值就是答案
*       设第一天是星期p, 则这n天有Ex=(n+p)/7个星期天，有Ey=(n+p-1)/7个星期六
*       ①：易得第一个星期天的记忆单词数：7-p+1 = 7+(1-p)
*       设g[Ex][k]为所有星期天所记单词数
*       g[Ex][k] = (7+(1-p))^k + (2*7+(1-p))^k + (3*7+(1-p))^k +...+ (Ex*7+(1-p))^k
*       由二次多项式得：
*       (Ex*7+(1-p))^k = C(k,0)*((1-p)^k) +...+ C(k,k)*(7^k)*(Ex^k)
*   ((Ex-1)*7+(1-p))^k = C(k,0)*((1-p)^k) +...+ C(k,k)*(7^k)*((Ex-1)^k)
*   ((Ex-2)*7+(1-p))^k = C(k,0)*((1-p)^k) +...+ C(k,k)*(7^k)*((Ex-2)^k)
*                ...                       ...
*        (1*7+(1-p))^k = C(k,0)*((1-p)^k) +...+ C(k,k)*(7^k)*1
*       所以得递推式：
*           g[Ex][k] = C(k,0)*((1-p)^k)*f[Ex][0] +...+ C(k,k)*(7^k)*f[Ex][k]
*       即在上面的矩阵基础上加一行即可求g[Ex](令n=Ex)：
*       |C(0,0) 0......................0 1 0|     |f[n  ][0]|     |f[n+1][0]|
*       |C(1,0) C(1,1) 0...............0 1 0|     |f[n  ][1]|     |f[n+1][1]|
*       |...................................|     |.........|     |.........|
*       |C(j,0) C(j,1)...C(j,j) 0......0 1 0|  *  |f[n  ][j]|  =  |f[n+1][j]|
*       |...................................|     |.........|     |.........|
*       |C(k,0) C(k,1) C(k,2).....C(k,k) 1 0|     |f[n  ][k]|     |f[n+1][k]|
*       |0.............................0 1 0|     |1        |     |1        |
*       |C(k,0)*((1-p)^k)...C(k,k)*(7^k) 0 0|     |g[n-1][k]|     |g[n  ][k]|
*       ②：易得第一个星期六的记忆单词数：7-p = 7+(-p)，同理可求所有星期六的记忆单词总数
*   于是问题解决。
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define M 15
#define LL long long
#define FF(i, n) for(int i = 0; i < n; i++)

int ans[M], mod = 1000000007;
int ret[M][M], C[M][M];
int init[M][M];

void ini(int n)
{
    memset(init, 0, sizeof(init));
    FF(i, n-1) FF(j, i+1)
        init[i][j] = C[i][j];
    FF(i, n) {
        ans[i] = 1;
        init[i][n-1] = 1;
    }
}

void matmul(int a[][M], int b[][M], int n)
{
    int tp[M][M] = {0};
    FF(i, n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j])
        tp[i][j] = (tp[i][j] + (LL)a[i][k]*b[k][j]) % mod;
    FF(i, n) FF(j, n) a[i][j] = tp[i][j];
}

void matmul(int a[], int b[][M], int n)
{
    int tp[M] = {0};
    FF(j, n) if(a[j]) FF(i, n) if(b[i][j])
        tp[i] = (tp[i] + (LL)b[i][j]*a[j]) % mod;
    FF(i, n) a[i] = tp[i];
}

void qmod(int n, int b)     //矩阵快速幂
{
    FF(i, n) FF(j, n) ret[i][j] = (i==j);
    for ( ; b; b >>= 1)
    {
        if (b & 1) matmul(ret, init, n);
        matmul(init, init, n);
    }
}

int cal(int a, int b)       //快速幂求(a^b) % mod
{
    int res = 1;
    for ( ; b; b >>= 1)
    {
        if (b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
    }
    return res;
}

int run(int n, int b, int x)
{
    qmod(n, b);
    matmul(ans, ret, n);
    return ans[x];
}

int main()
{
    int t, cc = 0, p, a, b, c, n, k, i, j;
    for (i = 0; i < M; i++) C[i][0] = C[i][i] = 1;
    for(i = 2; i < M; i++)
        for(j = 1; j < i; j++)
            C[i][j] = ((LL)C[i-1][j-1] + C[i-1][j]) % mod;
    char s[20];
    scanf("%d", &t);
    while (t--)
    {
        scanf("%s", s);
        if (s[0] == 'M') p = 1;
        else if (s[0] == 'T') {
            if (s[1] == 'u') p = 2;
            else p = 4;
        } else if (s[0] == 'W') p = 3;
        else if (s[0] == 'F') p = 5;
        else if (s[0] == 'S') {
            if (s[1] == 'a') p = 6;
            else p = 7;
        }
        scanf("%d%d", &n, &k);
        ini(k+2);
        a = run(k+2, n-1, k);

        ini(k+2);
        for (j = 0; j <= k; j++)
            init[k+2][j] = (LL)C[k][j]*cal(mod-p, k-j)%mod * cal(7, j) % mod;
        ans[k+2] = 0;
        b = run(k+3, (n+p)/7, k+2);

        ini(k+2);
        for (j = 0; j <= k; j++)
            init[k+2][j] = (LL)C[k][j]*cal((mod-p+1)%mod, k-j)%mod
             * cal(7, j) % mod;
        ans[k+2] = 0;
        c = run(k+3, (n+p-1)/7, k+2);

        int ans = (((LL)a-b-c)%mod + mod) % mod;
        printf("Case %d: %d\n", ++cc, ans);
    }
    return 0;
}