TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5409
  • 题目
  • P5409【欢乐的痛苦赛】简单的公式
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    问题描述

    nodgd在做题的时候,发现某道题的答案可以通过一个简单的公式算出来:

    \[ y\ =\ x_1\ \\&\ x_2\ \\&\ \dots\ \\&\ x_n \]

    其中 \(x_1,x_2,\dots,x_n\) 都是输入数据当中给出的,$y$是这道题的答案。

    当nodgd辛辛苦苦写完程序交上去的时候,发现这道题居然没有数据!内心充满正义的nodgd决定立刻生成一些数据,以防恶意提交;但这个数据又不能太简单,如果数据太简单就会让一些奇怪的程序能够通过。nodgd希望造出一些数据,满足以下条件:

    1. \(x_1,x_2,\dots,x_n\) 都是非负整数,且不超过$2^m-1$;
    2. 输入的前 \(k\) 个数 \(x_1,x_2,\dots,x_k\) 要交给nodgd全权负责,nodgd会给出这 \(k\) 个数的值;
    3. 公式计算的结果 \(y​\) 不超过nodgd的身高,即给定正整数 \(h​\) ,计算结果满足 \(y \leq h​\)

    nodgd当然知道如何生成数据,但是他想知道一共可以生成多少种不同的数据。只要两组数据的某个位置上的数不同就认为这两组数据不同,例如 \(n=3\) 时, \(\\{x_1,x_2,x_3\\}\)\(\\{1,2,3\\},\\{1,2,4\\},\\{3,2,1\\}\) 都是不同的数据。答案可能很大,所以只需要 \(\bmod\ 1,000,000,007\) 后的结果。

    输入格式

    输入共两行。

    第一行包含 $4$ 个整数 \(n,m,k,h\) ,含义如问题描述中所述。

    第二行 \(k\) 个数,表示nodgd钦定的数值,也就是的 \(x_1,x_2,\dots,x_k\) 的值。

    输出格式

    输出共一行。

    输出一行,一个整数,表示满足条件的不同的数据有多少种, \(\bmod\ 1,000,000,007\) 后的值。

    样例输入

    3 2 1 1
    3

    样例输出

    12

    提示

    输入输出样例1说明

    公式是

    \[ y\ =\ x_1\ \\&\ x_2\ \\&\ x_3 \]

    要满足每个数都不超过 $2m-1=22-1=3$ ,且 \(x_1=3,y\leq1\) 的条件。

    可以通过枚举得到所有符合条件的 $12$ 组数据:

    \[ \\{3,0,0\\},\\{3,0,1\\},\\{3,0,2\\},\\{3,0,3\\},\\\\ \\{3,1,0\\},\\{3,1,1\\},\\{3,1,2\\},\\{3,1,3\\},\\\\ \\{3,2,0\\},\\{3,2,1\\},\\{3,3,0\\},\\{3,3,1\\}.\\\\ \]

    数据规模与约定

    前 $10\%$ 的数据, \(n=4,\ m=2,\ k=0\)

    前 $30\%$ 的数据, \(n\leq 15,\ m=2\)

    前 $60\%$ 的数据, \(n\leq 15,\ m\leq 60\)

    全部测试数据, $1\leq n\leq1000,\ 1\leq m\leq 60,\ 0\leq k\leq n,\ 0\leq h,x_1,x_2,\dots,x_k\leq 2^m-1$ 。


    来源  感谢nodgd命题