记录编号	35230	评测结果	AAAAAAAAAA
题目名称	线性递推式	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-02-18 11:50:46	内存使用	0.30 MiB

#include <cstdio>
#include <cstring>
int n, i, j, u, v;
int f[20], g[20];
int a[20], b[20][20], c[20][20], d[20][20];
int p[10010];
long long k;
void copy() {
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            c[i][j] = d[i][j];
}
int main() {
    freopen("recursion.in", "r", stdin);
    freopen("recursion.out", "w", stdout);
    scanf("%d %lld", &n, &k);
    for(int i=0; i<=n; i++)
        scanf("%d", &a[i]);
    for(int i=0; i<n; i++)
        scanf("%d", &f[i]);
    f[n] = 1;
    memset(b, 0, sizeof(b));
    for(int i=0; i<=n-2; i++)
        b[i][i+1] = 1;
    for(int i=0; i<=n; i++)
        b[n-1][i] = a[i];
    b[n][n] = 1;
    k = k - (n - 1);
    for(int i=0; i<=n; i++)
        c[i][i] = 1;
    p[0] = 0;
    do {
        p[++p[0]] = k % 2;
        k = k / 2;
    } while(k != 0);
    for(int i=p[0]; i>0; i--) {
        memset(d, 0, sizeof(d));
        for(int j=0; j<=n; j++)
            for(int v=0; v<=n; v++) {
                for(int u=0; u<=n; u++)
                    d[j][v] += c[j][u] * c[u][v];
                d[j][v] %= 9973;
            }
        copy();
        memset(d, 0, sizeof(d));
        if(p[i] == 1) {
            for(int j=0; j<=n; j++)
                for(int v=0; v<=n; v++) {
                    for(int u=0; u<=n; u++)
                        d[j][v] += c[j][u] * b[u][v];
                    d[j][v] %= 9973;
                }
            copy();
        }
    }
    memset(g, 0, sizeof(g));
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            g[i] += f[j] * c[i][j] ;
    printf("%d\n", g[n-1] % 9973);
    return 0;
}