题解 | 前缀平方和序列

每日一题: 第三天()()()

题意:构造一个长度为n的数组,要求其前缀和数组中的元素均是平方数而且均小于给定的x,观察到n<=1e3,x<=1e6,由于前缀和元素均是平方数,所以sqrt(prei)<=1e3,明显可以n平方算法

考虑dpij表示前缀和第i个元素是j的平方,由于是正整数数组,所以前缀和必然越来越大,如果第i个元素是j,那么可以由dpi-1,1 dpi-1,2 ... dpi-1,j-1转移而来,暴力枚举是n三方,不可以接受,前缀和优化一下即可

(跑去写周赛了orz)

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int,int> PII;


const int INF = 0x3f3f3f3f;


void debug()
{
     cout<<"debug"<<endl;
}


class solution
{
    public:
        void solve();
        void ycl();
        solution(){};
};


LL power(LL a,LL b,LL p) { 
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % p) {
        if (b % 2) {
            res = 1LL * res * a % p;
        }
    }
    return res;
}

const int mod = 1e9+7;
const int N = 1e3+10;
int f[N][N];
void solution::solve()
{
    // a[i] = x*x-y*y
    // a[i] = (x+y)*(x-y)
    int n,x;cin>>n>>x;
    memset(f,0,sizeof 0);
    int mx = sqrt(x);
    int ans = 0;
    f[0][0]=1;
    for(int i=1;i<=n;i++) 
    {
        int res=0;
        for(int j=0;j<=mx;j++)
        {
            f[i][j] = (f[i][j]+res)%mod;
            res = (res+f[i-1][j])%mod;
            // cout<<i<<" "<<j<<" "<<res<<endl;
        }
    }
    for(int i=1;i<=mx;i++)
        ans = (ans+f[n][i])%mod;
    cout<<ans<<endl;
}


signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int T = 1;
    solution AC;
    //cin>>T;
    //AC.ycl();
    while(T --)
    {
        AC.solve();
    }
    return 0;
}