题解 | #前缀平方和序列#
前缀平方和序列
https://www.nowcoder.com/practice/5a4a7feaa70e45f1ad69ac86f0e4b246
前缀和必须是平方数，所以其实就是从 里按顺序挑
个，当作每一步前缀和，能挑多少种就是答案。
void solve(){
int n,x;cin>>n>>x;
int m=(int)sqrt((double)x);
while((ll)(m+1)*(m+1)<=x)++m;
while((ll)m*m>x)--m;
if(m<n){
cout<<0<<endl;
return;
}
vll f(m+1);
f[0]=1;
for(int i=1;i<=m;++i){
f[i]=f[i-1]*i%MOD;
}
vll inv(m+1);
inv[m]=qpow(f[m],MOD-2);
for(int i=m;i>0;--i){
inv[i-1]=inv[i]*i%MOD;
}
ll ans=f[m]*inv[n]%MOD*inv[m-n]%MOD;
cout<<ans<<endl;
}
查看12道真题和解析
