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

Input

2 7 2
1 1
1 2

Output

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 = ;

 LL n,N,M,C;

 struct Matrix{

     LL m[][];

     void init(){

         memset(m,,sizeof m);

     }

     void setOne(){

         init();

         for(int i = ; i < ; ++i) m[i][i] = ;

     }

     Matrix(){

         init();

     }

     Matrix operator*(const Matrix &rhs) const{

         Matrix ret;

         for(int k = ; k <= n; ++k)

             for(int i = ; i <= n; ++i)

                 for(int j = ; 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 = ; i <= n; ++i){

             for(int j = ; 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&) a = a*b;

         index >>= ;

         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 = ; i <= N; ++i){

             scanf("%I64d",&a.m[][i]);

             b.m[i+][i]++;

         }

         for(int i = ,tmp; i <= C; ++i){

             scanf("%d",&tmp);

             b.m[N +  - tmp][n]++;

         }

         if(M <= N){

             printf("%I64d\n",a.m[][M]%mod);

             continue;

         }

         quickPow(M - N);

         printf("%I64d\n",a.m[][n]%mod);

     }

     return ;

 }

 /*

 2 3 2

 1 1

 1 2

 3 5 3

 0 1 2

 1 2 3

 */

巴特西

CodeForcesGym 100735B Retrospective Sequence

Retrospective Sequence

Input

Output

Sample Input

Source

最新文章

热门文章