数据范围推断情况数

• ，下标为 的前缀和 需要为不大于 的正平方数，所以 的种类最多有 种。
• ，序列的长度不大，和前缀和种类规模相当，联想到可以用背包来求方案数。

动态规划求解

• 令 为前 个前缀和已经满足为不大于 的正平方数的要求， 为第 大的合法平方数的方案数。

• 初始化令 ，表示未取一个数的起始方案。

• 因为序列是正整数序列，所以第 位的前缀和一定小于第 位的前缀和，故可以得到状态转移方程 。

• 注意到这个转移方程和无穷背包的转移方程是很类似的，即观察到 ， 的转移项中包含了 的转移项中除 外的所有项，因此可以把状态转移方程变式为 。

• 令合法平方数种类为 ，则最后的答案为 。

#include <bits/stdc++.h>
using namespace std;

#define int long long 

const int N = 1e3+5,mod = 1e9+7;

int n,m;
int f[N][N];

signed main()
{
    cin>>n>>m;
    m = sqrt(m);
    f[0][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j] = (f[i-1][j-1] + f[i][j-1])%mod;
        }
    }
    int ans = 0;
    for(int i=1;i<=m;i++){
        ans = (ans + f[n][i])%mod;
    }
    cout<<ans;
}