CodeForcesGym 100735B Retrospective Sequence

Retrospective Sequence

Time Limit: Unknown ms

Memory Limit: 65536KB

This problem will be judged on CodeForcesGym. Original ID: 100735B
64-bit integer IO format: %I64d      Java class name: (Any)

 

Retrospective sequence is a recursive sequence that is defined through itself. For example Fibonacci specifies the rate at which a population of rabbits reproduces and it can be generalized to a retrospective sequence. In this problem you will have to find the n-th Retrospective Sequence modulo MOD = 1000000009. The first (1 ≤ N ≤ 20) elements of the sequence are specified. The remaining elements of the sequence depend on some of the previous N elements. Formally, the sequence can be written as Fm = Fm - k1 + Fm - k2 + ... + Fm - ki + ... + Fm - kC - 1 + Fm - kC. Here, C is the number of previous elements the m-th element depends on, 1 ≤ ki ≤ N.

 

Input

The first line of each test case contains 3 numbers, the number (1 ≤ N ≤ 20) of elements of the retrospective sequence that are specified, the index (1 ≤ M ≤ 1018) of the sequence element that has to be found modulo MOD, the number (1 ≤ C ≤ N) of previous elements the i-th element of the sequence depends on.

The second line of each test case contains N integers specifying 0 ≤ Fi ≤ 10, (1 ≤ i ≤ N).

The third line of each test case contains C ≥ 1 integers specifying k1, k2, ..., kC - 1, kC (1 ≤ ki ≤ N).

 

Output

Output single integer R, where R is FM modulo MOD.

 

Sample Input

Input

2 2 2
1 1
1 2

Output

1

Input

2 7 2
1 1
1 2

Output

13

Input

3 100000000000 3
0 1 2
1 2 3

Output

48407255

Source

KTU Programming Camp (Day 1)

 

解题：矩阵快速幂

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1000000009;
LL n,N,M,C;
struct Matrix{
    LL m[60][60];
    void init(){
        memset(m,0,sizeof m);
    }
    void setOne(){
        init();
        for(int i = 0; i < 60; ++i) m[i][i] = 1;
    }
    Matrix(){
        init();
    }
    Matrix operator*(const Matrix &rhs) const{
        Matrix ret;
        for(int k = 0; k <= n; ++k)
            for(int i = 0; i <= n; ++i)
                for(int j = 0; j <= n; ++j)
                    ret.m[i][j] = (ret.m[i][j] + m[i][k]*rhs.m[k][j]%mod)%mod;
        return ret;
    }
    void print(){
        for(int i = 0; i <= n; ++i){
            for(int j = 0; j <= n; ++j)
                cout<<m[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
    }
};
Matrix a,b;
void quickPow(LL index){
    //Matrix ret;
    //ret.setOne();
    while(index){
        if(index&1) a = a*b;
        index >>= 1;
        b = b*b;
    }
    //a = a*ret;
}
int main(){
    while(~scanf("%I64d%I64d%I64d",&N,&M,&C)){
        a.init();
        b.init();
        n = N;
        for(int i = 1; i <= N; ++i){
            scanf("%I64d",&a.m[0][i]);
            b.m[i+1][i]++;
        }
        for(int i = 1,tmp; i <= C; ++i){
            scanf("%d",&tmp);
            b.m[N + 1 - tmp][n]++;
        }
        if(M <= N){
            printf("%I64d
",a.m[0][M]%mod);
            continue;
        }
        quickPow(M - N);
        printf("%I64d
",a.m[0][n]%mod);
    }
    return 0;
}
/*
2 3 2
1 1
1 2

3 5 3
0 1 2
1 2 3
*/