Expert.
Put your skills to the test.

Problem summary

The first k terms and k fixed coefficients are bits. For i>k, a[i] is the sum m[j]·a[i−k+j−1] modulo 2. Answer many queries asking for a[n] with different initial terms.

Source clarification. The PDF header prints 7 January 2023 although Arena catalogs this in the 2024 season. The input prose says k numbers on a query line, but explicitly lists n and k initial terms; the official example confirms k+1 numbers.

Constraints

1 ≤ T ≤ 500000; 1 ≤ k ≤ 20; all coefficients and initial terms are bits; 1 ≤ n ≤ 1000000000.

Worked example

Independent small example.

2 2
1 1
3 1 0
4 1 0

1
1

Solution analysis

1. Encode a window of k consecutive terms by a k-bit integer, with the oldest term in bit 0. Its successor shifts right and inserts the parity of state AND coefficientMask into bit k−1. This transition depends only on the fixed coefficients, so all queries share it.
2. There are at most 2²⁰ states. Precompute jump[b][s], the state after 2^b transitions, for b=0..29. The composition rule jump[b][s]=jump[b−1][jump[b−1][s]] costs only two array accesses.
3. If n≤k, return the corresponding initial bit. Otherwise advance the initial state by n−k transitions and read its newest bit. For coefficients (1,1) and initial terms (1,0), successive terms are 1,1,0,..., so both queries in the displayed independent example return 1.

Why it works

The transition computes exactly the recurrence term and retains the k−1 most recent old terms. Induction on b proves the jump table advances exactly 2^b terms. Decomposing n−k into binary therefore reaches the window ending at n, whose newest bit is a[n]. Direct indexing handles earlier terms.

Watch out. Keep coefficient order aligned with the oldest-to-newest bit order. A query contains n plus k initial bits.

An independently written complete program with standard headers.

// Key idea: The transition computes exactly the recurrence term and retains the k−1 most recent old
// terms. Induction on b proves the jump table advances exactly 2^b terms.
#include<cstdint>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int queries,k;
    cin>>queries>>k;
    int mask=0;
    for(int i=0;i<k;++i){
        int bit;
        cin>>bit;
        mask|=bit<<i;
    }
    int states=1<<k;
    vector<vector<int>>jump(30,vector<int>(states));
    vector<unsigned char>parity(states);
    for(int s=1;s<states;++s){
        parity[s]=parity[s>>1]^(s&1);
    }
    for(int s=0;s<states;++s){
        jump[0][s]=(s>>1)|(int(parity[s&mask])<<(k-1));
    }
    for(int b=1;b<30;++b){
        for(int s=0;s<states;++s){
            jump[b][s]=jump[b-1][jump[b-1][s]];
        }
    }
    while(queries--){
        int n,state=0;
        cin>>n;
        for(int i=0;i<k;++i){
            int bit;
            cin>>bit;
            state|=bit<<i;
        }
        if(n<=k){
            cout<<((state>>(n-1))&1)<<'\n';
            continue;
        }
        int steps=n-k;
        for(int b=0;b<30;++b){
            if((steps>>b)&1){
                state=jump[b][state];
            }
        }
        cout<<(state>>(k-1))<<'\n';
    }
}