#P14672. [Bulgarian2024 school]calculations

    ID: 13888 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 6 上传者: 标签>CF2100提高线性递推状态编码倍增跳转预计算转移

[Bulgarian2024 school]calculations

题目描述

在经历了两场表现不佳的 Codeforces 轮次之后,Elena 开始怀疑自己为什么会相信自己能做信息学题,于是决定回到数学的怀抱。作为热身,她给自己出了下面这道简单题:

计算 ana_n,其中:

  • 前 kk 个元素分别为 a1,a2,…,aka_1,a_2,\dots,a_k;

  • 对于 i>ki>k,有

    $$a_i=(m_1\times a_{i-k}+m_2\times a_{i-k+1}+\dots+m_k\times a_{i-1})\bmod 2;$$
  • x mod 2x\bmod 2 表示 xx 除以 22 的余数。

尽管她并不情愿,Elena 还是得检查自己的计算结果,而这用程序来做最方便。请你编写程序 calculations,对于不同的 n,a1,a2,…,akn,a_1,a_2,\dots,a_k,计算对应的 ana_n。

输入格式

第一行输入两个正整数 TT 和 kk,分别表示需要解决多少组询问,以及已知多少个初始值。

第二行输入 m1,m2,…,mkm_1,m_2,\dots,m_k,即题目中递推关系里的系数。

接下来的 TT 行中,每行给出 k+1k+1 个数: n,a1,a2,…,akn,a_1,a_2,\dots,a_k,分别表示要查询第几个元素,以及该组询问中数列的前 kk 项。

输出格式

对于每组询问,输出一行一个整数,表示对应的答案。

数据范围

  • 1≤T≤5×1051\le T\le 5\times 10^5
  • 1≤k≤201\le k\le 20
  • 对所有 i=1,2,…,ki=1,2,\dots,k,有 0≤ai,mi≤10\le a_i,m_i\le 1
  • 1≤n≤1091\le n\le 10^9

样例 #1

输入 #1

10 4
0 1 1 0
8 0 0 1 1
4 1 1 1 1
6 1 1 1 1
3 0 1 1 1
7 0 1 1 0
4 0 0 1 1
1 0 1 1 0
5 1 0 1 1
2 1 0 0 1
3 0 0 0 1

输出 #1

1
1
0
1
0
1
0
1
0
0

子任务

子任务 分值 需要通过的前置子任务 额外限制
1 0 - 样例测试。
2 10 1 n,T≤104n,T\le 10^4
3 20 1-2 T≤5×104T\le 5\times 10^4
4 30 1-3 T≤105T\le 10^5
5 40 1-4 无额外限制

只有当某个子任务以及它所依赖的全部前置子任务都通过时,才会获得该子任务的分数。