bzoj1025: [SCOI2009]游戏(DP)

　　题目大意：将长度为n的排列作为1,2,3,...,n的置换，有可能置换x次之后，序列又回到了1,2,3,...,n，求所有可能的x的个数。

　　看见这种一脸懵逼的题第一要务当然是简化题意。。。我们可以发现，序列回到原状的次数就是每个循环的规模（即在循环中的数字个数）的lcm，而且因为有n个数，显然所有循环的规模之和就是n，那么问题就被简化成了a1+a2+a3+...+ak=n，求lcm(a1,a2,a3,...,an)的个数。

　　现在题意已经清楚多了，那咋写呢QAQ

　　我们把一个数分解质因数，p为质数，那么A=p1^m1*p2^m2*p3^m3*...*ph^mh，我们令a1=p1^m1，a2=p2^m2，...，ah=ph^mh，易证a1+a2+a3+...+ah<=n（分<和=两种情况讨论），则A为一个可行解。

　　于是问题又变成了求有多少种a1+a2+a3+...+ah<=n。

　　即有多少种(m1,m2,m3,...,mh)使p1^m1+p2^m2+p3^m3+...+ph^mh<=n。

　　令f[i][j]为前i个质数，p1^m1+p2^m2+p3^m3+...+pi^mi和为j的方案数，则有：

　　f[i][j]=f[i-1][j]【这个质数不用】+sigma(f[i-1][j-p[i]^k])【j-p[i]^k>=0】

　　tot为n以内的质数个数，则答案为sigma(f[tot][i])【0<=i<=n】

代码如下：

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#define ll long long

using namespace std;

ll f[][],ans;

int n,p[],tot;

bool v[];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    if(!v[i])

    {

        p[++tot]=i;

        for(int j=;j*i<=n;j++)v[i*j]=true;

    }

    f[][]=;

    for(int i=;i<=tot;i++)

    for(int j=;j<=n;j++)

    {

        f[i][j]=f[i-][j];

        for(int k=,sum=;j-sum*p[i]>=;k++)

        {

            sum*=p[i];

            f[i][j]+=f[i-][j-sum];

        }

    }

    for(int i=;i<=n;i++)

    ans+=f[tot][i];

    printf("%lld\n",ans);

}