题解 | 前缀平方和序列

#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;
const ll INF = 1e18;
ll a[N];
ll dp[N][N];
ll pre[N];
ll n,x;
void solve()
{

    cin>>n>>x;



    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            for(int j=1;j*j<=x;j++)
            {
                dp[i][j]=1;
            }
        }
        else 
        {
            for(int j=1;j*j<=x;j++)
            {
                pre[j] = (pre[j-1]+dp[i-1][j])%mod;
            }
            for(int j=i;j*j<=x;j++)
            {
                dp[i][j] = pre[j-1];
            }
        }
    }

    ll res = 0;
    for(int i=1;i*i<=x;i++)
    {
        res = (res+dp[n][i])%mod;
    }

    cout<<res<<'\n';


}
    


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();

    }


    return 0;
}

题解似乎很少像我一样用dp做的，这里提供一种dp做法，dp[i][j]为长度为i ，以sum=j*j作为前缀和，那么不难发现，对于第i个长度，sum=j*j 其实就是i-1长度下，从1到j-1的所有可能的总和，这里可以用前缀和优化复杂度到O(n*sqrt(x));