bzoj1025 [SCOI2009]游戏 动态规划

题目描述

对于一些长度为n的排列，将其作为一个置换，那么可能有一个自置换的次数使其回到1,2,3,...,n的情况。求对于所有能够回到1,2,3..,n的排列，不同的次数共有多少种。

题解来自黄学长

这道题可以转换一下。

试想每一个对应关系a-b为从a->b的一条边，

那么图中一定存在n条边且每个点入度出度都为1，

易证一定存在一个或几个环。

实际上排数就是这几个环大小的最小公倍数。

即求和为n的数列的最小公倍数种数。

那么可以直接DP

#include<algorithm>
#include<cstdio>
#include<cstdio>
using namespace std;
int n,tot;
int pri[1005];
long long ans,f[1005][1005];
bool vis[1005];
void getpri(){
    for(int i=2;i<=1000;i++){
        if(!vis[i])pri[++tot]=i;
        for(int j=1;j<=tot&&pri[j]*i<=1000;j++){
            vis[pri[j]*i]=1;
            if(i%pri[j]==0)break;
        }
    }
}
int main(){
    scanf("%d",&n);
    getpri();
    f[0][0]=1;
    for(int i=1;i<=tot;i++){
        for(int j=0;j<=n;j++)f[i][j]=f[i-1][j];
        for(int j=pri[i];j<=n;j*=pri[i])
            for(int k=0;k<=n-j;k++)
                f[i][k+j]+=f[i-1][k];
    }
    for(int i=0;i<=n;i++)ans+=f[tot][i];
    printf("%lld",ans);
}