首页 > 试题广场 >

前缀平方和序列

[编程题]前缀平方和序列
  • 热度指数：364 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}设正整数序列 \{a_1,a_2,\dots,a_n\} 的前缀和为 s_i=\sum_{j=1}^{i}a_j。若对于所有 1\leqq i\leqq n，s_i 都是完全平方数，则称该序列为一条前缀平方序列。
\hspace{15pt}给定两个正整数 n 与 x，请你计算满足：
\hspace{23pt}\bullet\, 序列长度为 n；
\hspace{23pt}\bullet\, 对任意前缀和 s_i 均有 1\leqq s_i\leqq x；
\hspace{15pt}的前缀平方序列数量。结果对 P=1\,000\,000\,007 取模。

输入描述:
\hspace{15pt}在一行上输入两个整数 n,x\left(1\leqq n\leqq 10^3,\ 1\leqq x\leqq 10^6\right)。


输出描述:
\hspace{15pt}输出一个整数，表示满足条件的序列数量模 P 的值。
示例1

输入

4 26

输出

5
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

来自：2025年秋招-中国联...
难度：
0条回答 106浏览

热门推荐

相关试题

前缀平方和序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号