#P3780. 数字统计

    ID: 2983 传统题 1000ms 128MiB 尝试: 148 已通过: 42 难度: 6 上传者: 标签>CF2000提高数位 DP自动机 DP上界限制状态滚动数组高精度加法

数字统计

题目描述

小 A 正在研究一些数字统计问题。有一天他突然看到了一个这样的问题:

将 [L,R][L,R] 中的所有整数用 mm 位二进制数表示(允许出现前导 00)。现在将这些数中的每一个作如下变换:

从这个数的最低两位开始,如果这两位都是 00,那么 x=1x=1,否则 x=0x=0。现在将这两位删去,然后将 xx 放在原来最低位的位置上。重复这个变换直到这个数只剩下一位为止。

例如 0100101001 的变换过程如下:

$01001 \rightarrow 0100 \rightarrow 011 \rightarrow 00 \rightarrow 1$

现在的问题是变换后的所有数中,值为 yy(yy 为 00 或 11)的有多少个?

小 A 不会了,他想让你帮助他完成这个问题。

输入格式

输入文件包含多组测试数据。

第一行,一个整数 TT,表示测试数据的组数。

接下来的 TT 节,每节对应一组测试数据,格式如下:

第一行,两个整数 m,ym,y。

第二行,两个 mm 位二进制数 L,RL,R。

输出格式

对于每组测试数据,输出一行,一个二进制数,表示该组测试数据中 [L,R][L,R] 中的所有整数变换后的值为 yy 的个数。这里的二进制数不允许出现前导 00。

1
3 1
001 101
11

数据规模与约定

对于 100%100\% 的数据,1≤m≤2001 \le m \le 200,1≤T≤501 \le T \le 50。