题目大意
有一个数列，初始时只有一个数 \(X\)。你可以对它进行一种操作：设末尾的数为 \(Y\)，从 \(1 \sim \sqrt{Y}\) 中选一个数加到数列的末尾。如此进行 \(10^{100}\) 次操作，问数列一共有多少种可能的状态。
解法
考虑 DP。
设 \(dp_i\) 表示以数字 \(i\) 开头的数列可能的状态。设 \(i\) 的下一个位置上的数为 \(j\)，那么显然 \(dp_i = \sum\limits_{j = 1}^{\sqrt{i}}{dp_j}\)。预处理出 \(dp_i\)，询问时，答案为 \(dp_x\)。但此时的时间复杂度为 \(\Theta(T+X\sqrt{X})\)，对于 \(X \le 9 \times10^{18}\) 这种极大的数据范围来说，显然是不可接受的，所以我们需要考虑优化。
设 \(j\) 的下一个位置上的数为 \(k\)，根据前面的转移方程，容易得出 \(dp_j = \sum\limits_{k = 1}^{\sqrt{i}}{dp_k}\)。我们可以考虑算贡献。贡献是指 \(dp_k\) 对 \(dp_j\) 的影响，也就是在所有的 \(dp_j\) 中，有多少种状态含有 \(dp_k\)。而 \(k\) 的范围是 \(1 \sim \sqrt{j}\)，也就是 \(\sqrt{j} \ge k\) 的 \(dp_j\) 才会被 \(dp_k\) 所影响，那么对于每一个 \(dp_k\)，所能贡献的范围就是 \(k^2 \sim \sqrt{i}\)。这里的 \(\sqrt{i}\) 就是所有 \(j\) 的范围。这样只需预处理出 \(dp_{1 \sim \sqrt[4]{x}}\) 的值，每次询问时，枚举 \(1 \sim \sqrt[4]{x}\)，也就是 \(k\)，将所有 \(dp_k\) 的贡献加起来即为答案。
这里有几点细节需要注意，由于此题数据范围过大，sqrt() 的精度可能不够，需要将开根的数强制转为 long double 才行。
AC Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int t, x, dp[N], f[N];
signed main()
{
dp[1] = 1;
for(int i = 2; i <= 1e5; i++)//预处理
for(int j = 1; j <= sqrt((long double)i); j++)
dp[i] += dp[j];
cin >> t;
while(t--)
{
cin >> x;
int y = sqrt((long double)x);
int ans = 0;
for(int i = 1; i <= sqrt((long double)y); i++)
ans += (y - i * i + 1) * dp[i];//dp[i]产生的贡献的范围是i * i ~ sqrt(sqrt(x))
cout << ans << "\n";
}
return 0;
}