zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const ll N=50005;
ll f[2][N];
ll g[2][N];
ll h[N];
ll n,m;
int main(){
    scanf("%lld",&n);m=sqrt(n);
    f[0][0]=1;
    int now=0,now1=0;
    for (ll u=1;u<=m;u++){
        now^=1;
        for (ll i=0;i<u;i++) f[now][i]=f[now^1][i];
        for (ll i=u;i<=n;i++) f[now][i]=(f[now][i-u]+f[now^1][i])%MOD;
    }
    m++;
    g[0][0]=1;h[0]=1;
    for (ll u=1;u<=m;u++){
        now1^=1;
        for (ll i=0;i<=n;i++)
        {
            g[now1][i]=0;
            if (i>=m) g[now1][i]=(g[now1][i]+g[now1^1][i-m])%MOD;
            if (i>=u) g[now1][i]=(g[now1][i]+g[now1][i-u])%MOD;
            h[i]=(h[i]+g[now1][i])%MOD;
        }
    }
    ll ans=0;
    for (ll u=0;u<=n;u++)   ans=(ans+f[now][u]*h[n-u]%MOD)%MOD;
    printf("%lld\n",ans);
}
51nod 1259 整数划分-V2
comment评论
Search
search