可设 \(f_i\) 为以 \(i\) 开头的方案数,由于最后由于操作数很多所以不用考虑还剩多少次操作,显然可得状态转移方程 \(f_i=\sum\limits_{j=1}^{\sqrt i}f_j\),时间复杂度 \(O(T+ X\sqrt X)\),空间复杂度 \(O(X)\),无法接受。
考虑如何更优,可以发现在 \(T\) 次询问中,每次可以直接转移,因此仅需要预处理 \(1\sim \sqrt X\) 区间的 \(f\),这样让空间降下来了,但是时间复杂度无法接受。
既然 \(f_i=\sum\limits_{j=1}^{\sqrt i}f_j\),那么在每次询问中最好的情况是直接知道 \(\sum\limits_{j=1}^{\sqrt i}f_j\) 的值,考虑计算出 \(1\sim \sqrt[4]{X}\) 的值对所有 \(f_j\) 的影响,不难得出 \(k\) 的第一次造成影响应从 \(k^2\) 起至 \(\sqrt[4]{X}\),则将出现次数乘上方案数即为最终答案,答案为 \(\sum\limits_{k=1}^{\sqrt[4]{X}}(f_k\times(\sqrt X - k^2+1))\)。
注意需要提前预处理 \(1\sim \sqrt[4]{X}\) 的 \(f\) 值。此题由于数据范围过大,直接用 sqrt()
肯定有误差,需要先强制转 long double
类型。
#include<bits/stdc++.h>
#define N 2000005
#define mod 998244353
#define int long long
using namespace std;
int n,m,dp[N],f[N];
signed main(){
int T;
cin>>T;
f[1]=1;
for(int i=2;i<=500000;i++){
for(int j=1;j<=sqrt((long double)i);j++) f[i]=(f[i]+f[j]);
}
while(T--){
cin>>n;
int res=0;
int k=sqrt((long double)n);
for(int i=1;i<=(int)sqrt((long double)k);i++){
dp[i]=f[i]*(k-i*i+1);
res=(res+dp[i]);
}
cout<<res<<endl;
}
}
标签:long,limits,int,题解,sum,sqrt,abc243,Sqrt,复杂度
From: https://www.cnblogs.com/Telsif/p/18002016