Family of Recurrences
All submissions for this problem are available.
Suppose we have recurrences of the following form, characterized by three parameters m, sigma1..m and f0..m-1, where m > 0 and sigmai is a binary variable (1 <= i <= m).
A sequence of number s can be generated as followings:
- if i < m, then si = fi
- otherwise, i.e. i >= m, si = fi - 1 * sigma1 + ... + fi - j * sigmaj + ... + fi - m * sigmam
Given m, n, sigma1..m and f0..m-1, compute sn modulo 10^9 + 7.
First line of input contains a positive interger T, then T testcases follow.
For each testcase, first line contains positive integer m and non-negative integer n
separated by a single space. Second line contains m integers of f0..m-1, separated by single space. Third line contains m numbers of sigma1..m, separated by single space.
For each testcase, output should contain a single number sn modulo 10^9 +7 followed by a newline.
1 <= T <= 20
1 <= m <= 100
0 <= n <= 10^9
-10^9 <= fi <= 10^9
sigmai = 0 or 1
Input: 2 2 100 1 1 1 1 3 10 1 1 1 1 1 1 Output: 782204094 193
Problem Setter : Asif Haque
|Tags||kan13acm, matrix-expo, medium, shangjingbo|
|Time Limit:||1.80905 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.