#2134231391. [NOIP 2021] 数列

内存限制:512 MiB 时间限制:1000 ms 输入文件:sequence.in 输出文件:sequence.out
题目类型:传统 评测方式:文本比较
上传者: j27eGU

题目描述

一. 题目概况

中文题目名称 数列
英文题目与子目录名
可执行文件名
输入文件名
输出文件名
每个测试点时限
测试点数目
测试点分值
附加样例文件
结果比较方式 全文比较(过滤行末空格)
题目类型 传统
运行内存上限

二. 提交源程序文件名

对于C++语言
对于C语言
对于pascal语言

2.数列

给定整数 ,和一个长度为 的正整数数组

对于一个长度为 ,下标从 开始且每个元素均不超过 的非负整数序列 ,我们定义它的权值为

当这样的序列 满足整数 的二进制表示中 的个数不超过 时,我们认为 是一个合法序列。

计算所有合法序列 的权值和对 取模的结果。

输入格式

输入第一行是三个整数

第二行 个整数,分别是

输出格式

仅一行一个整数,表示所有合法序列的权值和对 取模的结果。

样例

样例#1

输入样例#1

5 1 1
2 1

输出样例#1

40

样例#2

输入样例#2

见附件中的 sequence/sequence2.in

输出样例#2

见附件中的 sequence/sequence2.ans

数据范围与提示

【样例解释 #1】

由于 ,而且由 知道 ,合法的 只有一种可能:,这要求 中必须有 ,于是有 种可能的序列,每种序列的贡献都是 ,权值和为

【数据范围】

对所有测试点保证

测试点

原题链接:http://luogu.com.cn/problem/P7961