首页 > 试题广场 >

前缀平方和序列

[编程题]前缀平方和序列
  • 热度指数：398 时间限制：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
算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-07-14 18:12:48
题目链接 前缀平方和序列 题目描述 一个正整数序列 被称为 前缀平方序列，如果其所有前缀和 都是完全平方数。 给定两个正整数 和 ，请计算满足以下条件的前缀平方序列的数量： 序列长度为 。 总和 。 结果需要对 取模。 输入: 一行输入两个整数 。 输出: 输出一个整数，表示满足条 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 冷艳的西红柿刷牛客
发表于 2025-10-23 10:47:12
#include <iostream> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const ll p = 1000000007; ll f 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-08-29 10:03:15
题目链接 前缀平方和序列 题目描述 设一个正整数序列 的前缀和为 。若对于所有的 ， 都是完全平方数，则称该序列为一条前缀平方序列。 给定两个正整数 与 ，请你计算满足以下两个条件的前缀平方序列的数量： 序列长度为 。 对任意前缀和 均有 。 结果对 取模。 解题思路 这是一个计 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

相关试题

前缀平方和序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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