BZOJ-1025: [SCOI2009]游戏

[文章目录]

Description

windy学会了一种游戏。对于1到N这N个数字,都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1,2,3,……,N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为1,2,3,……,N。现在windy想知道,对于所有可能的对应关系,有多少种可能的排数。1 <= N <= 1000

最后排数是所有置换群大小的lcm加1,对于lcm,只有每个质因子的最大次幂有贡献,并且耗费的最少个数提供质因子的k次幂的方案为:构造一个大小为质因子的k次幂的置换。
将每个质因子的某次幂看成物品,大小看成体积,那么答案就是选物品使其体积和不超过N的方案数,跑背包即可。复杂度O(n^2logn)

#include <cstdio>
using namespace std;
typedef long long ll;
int n,pri[1100],cnt;
ll f[1100];
bool v[1100];
void init()
{
    int i,j;
    for(i=2;i<=n;++i)
    {
        if(!v[i]) pri[++cnt]=i;
        for(j=1;j<=cnt&&i*pri[j]<=n;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
int main()
{
    scanf("%d",&n);
    init();
    int i,j,k;
    f[0]=1;
    for(i=1;i<=cnt;++i)
    {
        for(k=n;k>=pri[i];--k)
            for(j=pri[i];j<=k;j*=pri[i])
                f[k]+=f[k-j];
    }
    ll ans=0;
    for(i=0;i<=n;++i) ans+=f[i];
    printf("%lld",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注