M_sea

洛谷4161 [SCOI2009]游戏
LuoguBZOJ分析事实上观察题目就可以发现,行数就是几个置换大小的$\text{lcm}$。然后就可以转换成和...
扫描右侧二维码阅读全文
11
2019/01

洛谷4161 [SCOI2009]游戏

Luogu

BZOJ

分析

事实上观察题目就可以发现,行数就是几个置换大小的$\text{lcm}$。

然后就可以转换成和为$n$的数列的$\text{lcm}$的种数。

再转换一下,变成了求有多少组$a_i$,满足$\sum p_i^{a_i}\leq n$。

$\text{大力dp}$一下就好了啊qwq。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000+10;

int v[MAXN],p[MAXN],cnt=0;

inline void sieve(int n) {
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

ll f[MAXN][MAXN];

int main() {
    int n=read(); sieve(n);
    f[0][0]=1;
    for (re int i=1;i<=cnt;++i) {
        for (re int j=0;j<=n;++j) f[i][j]=f[i-1][j];
        for (re int j=p[i];j<=n;j*=p[i])
            for (re int k=0;k<=n-j;++k)
                f[i][j+k]+=f[i-1][k];
    }
    ll ans=0;
    for (re int i=0;i<=n;++i) ans+=f[cnt][i];
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 01 月 23 日 01 : 03 PM

1 条评论

  1. smy

    怎么这都会

发表评论