首页 > 前缀平方和序列

憨憨的竹林

发表于 2026-05-03 00:42:56

好久没写题解了，这题简单就随手水一下好了当固定的时候，其实就也固定了，所以考虑有多少种前缀平方序列，其实就是在考虑有多少种序列，而序列长度为，而由于，所以满足条件的可选最多有个，所以此时就有了种挑选数字的方案，而又由于题目要求都是正整数，且有，所以序展开全文

烟尘墨

发表于 2024-07-12 17:01:08

数据范围推断情况数，下标为的前缀和需要为不大于的正平方数，所以的种类最多有种。，序列的长度不大，和前缀和种类规模相当，联想到可以用背包来求方案数。动态规划求解令为前个前缀和已经满足为不大于的正平方数的要求，为第大的合法平方数的方案数。初始化展开全文

AliLexiWalker

发表于 2026-05-03 01:20:14

前缀和必须是平方数，所以其实就是从里按顺序挑个，当作每一步前缀和，能挑多少种就是答案。 void solve(){ int n,x;cin>>n>>x; int m=(int)sqrt((double)x); while((ll)(m+1)*( 展开全文

飞鸢泛惊鸿

发表于 2026-05-03 01:07:37

import sys from math import sqrt,comb input=sys.stdin.readline MOD=10**9+7 def solve(): n,x=map(int,input().split()) m=int(sqrt(x)) while 展开全文

小男娘

发表于 2026-05-03 00:23:36

注意到答案为喵~ #include <cmath> #include <iostream> using namespace std; using ll = long long; const int MOD = 1e9 + 7; ll Pow(ll a, int b) 展开全文

IA3000

发表于 2026-05-03 01:28:52

#include <iostream> #include <cmath> using namespace std; const int mod = 1e9 + 7; const int N = 1e3 + 5; int fac[N]; int invfac[N]; in 展开全文

此在Dasein

发表于 2026-05-03 03:10:05

问题分析该问题的核心在于对“前缀平方序列”定义的转化。给定长度为的正整数序列，其前缀和定义为。题目要求必须满足以下三个约束条件：平方数约束：每个必须是一个完全平方数。正整数约束：由于，前缀和序列必须是严格单调递增的，即。上界约束：所有前缀和不得超过，即。令，其展开全文

chenlan114

发表于 2026-05-03 11:16:32

#include<bits/stdc++.h> using namespace std; using ll=long long; const ll N=1e3+1,mod=1e9+7; ll fact[N]; //阶乘 ll in_fact[N]; //阶乘逆展开全文

quchen666

发表于 2026-05-03 12:23:15

#include <bits/stdc++.h> using namespace std; const int N=1e3+10; const int mod = 1e9+7; typedef long long ll; typedef unsigned long long ull; c 展开全文

kendas

发表于 2026-05-03 19:02:58

每日一题: 第三天()()() 题意:构造一个长度为n的数组,要求其前缀和数组中的元素均是平方数而且均小于给定的x,观察到n<=1e3,x<=1e6,由于前缀和元素均是平方数,所以sqrt(prei)<=1e3,明显可以n平方算法考虑dpij表示前缀和第i个元素是j的平方,由于是正展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛