#PQJ117x6211. QOJ 117_6211
QOJ 117_6211
江苏省省队第一轮选拔赛
第一试 位运算 位运算 【故事背景】 JYY 最近在研究位运算。他发现位运算中最有趣的就是异或(xor)运算。 对于两个数的异或运算,JYY 发现了一个结论:两个数的异或值为0 当且仅当他 们相等。于是JYY 又开始思考,对于N 个数的异或值会有什么性质呢? 【问题描述】 JYY 想知道,如果在0 到R-1 的范围内,选出N 个不同的整数,并使得这N 个整数的异或值为0,那么一共有多少种选择的方法呢?(选择的不同次序并不 作重复统计,请参见样例) JYY 是一个计算机科学家,所以他脑海里的R 非常非常大。为了能够方便的 表达,如果我们将R 写成一个0-1 串,那么R 是由一个较短的0-1 串S 重复K 次 得到的。比如,若S=“101”,K=2,那么R 的2 进制表示则为“101101”。 由于计算的结果会非常大,JYY 只需要你告诉他选择的总数对109+7 取模的 结果即可。 【输入格式】 从文件binary.in 中读入数据。 第一行包含两个正整数N 和K。 接下来一行包含一个由0 和1 组成的字符串S。 我们保证S 的第一个字符一定为1。 【输出格式】 输出到文件binary.out 中。 输出文件包含一行一个整数,表示选择的方案数对109+7 取模的值。 【样例输入1】 3 1 100 【样例输出1】 1 【样例输入2】 5 100 1
江苏省省队第一轮选拔赛
第一试 位运算 【样例输出2】 598192244 【样例说明】 对于第一个样例,唯一的一种选择方法是选择 {1, 2, 3}。 【数据规模与约定】 测试点 N K |S| 1 𝑁= 3 𝐾= 1 𝑆= 10 2 𝐾= 10000 1 ≤𝑆≤50 3,4,5 𝑁= 5 1 ≤𝐾≤20 6 𝑁= 4 1 ≤𝐾≤104 7,8,9,10 3 ≤𝑁≤7