自动搬运

查看原文

来自洛谷，原作者为

	灵乌路空 已退役 | 东方众OIer交流群 (幻想乡养老院) : 691090556

搬运于2025-08-24 21:57:10，当前版本为作者最后更新于2019-08-13 11:24:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先无良宣传一下博客 $wwwwww$
文章列表 - 地灵殿 - 洛谷博客

知识点: 问题转化 , 背包DP

• 原题面:

  P4161 [SCOI2009]游戏

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

  原题面非常神仙不可做,
  考虑对题目进行转化.

• 一次转化 :

  从图的角度 , 对题面进行转化:

  • 有 $n$ 个点和 $n$ 条有向边
    点从$1 \sim n$ 进行编号
    每个点只有一条入边和一条出边 , (允许自环),
    每个点按照出边的方向进行转移.

    边可以任意连接,
    不同的连接方式 , 回到原状态的步数不等
    求回到原状态需要的 不同的步数 的数量 .

  再次分析:

  • 即在图中构建 环
    使每个点都位于 一个环 中

  • 设 $i$ 点所在环的环长为 $circle\_length[i]$
    最后回到原状态的步数
    显然,即 : $\operatorname{lcm}(circle\_length[i]) \ \ (i\in [1,n])$ ;

  • 现在 原题面要求得的 "排数" ,
    即 转化后要求的 不同的步数 的数量,
    即 不同的 环长的 $\operatorname{lcm}$ 数

• 二次转化 :

  从数学角度进行思考:

  • 因为只有 $n$ 条边,
    显然有 , $\sum\limits_{i=1}^{n}(circle\_length[i]) = n$
    即: 所有环长之和 $=n$ (包括 环长为1 的自环)

  • 则问题可进一步转化:
    构造 若干 和为 $n$ 的数
    使其不同的 $\operatorname{lcm}$ 数尽可能地多

  考虑怎样才能使 $\operatorname{lcm}$ 数尽可能多:

  • 如果 每次构造时,
    都使这些数全都 互质
    那么他们的 $\operatorname{lcm}$ 每次都是不同的.

  怎样使这些数全部互质 ?

  • 显然, 可以将他们构造成 不同质数的幂
    即: $\large p^k$ 的形式 $\ (k\in N \ \text{且有}\ p^k\le n)$
    ($N$ 为自然数集)

• 三次转化:

  由于要使构造的数 和为 $n$
  则可以选择的质数 $p \in [2,n]$ ,
  且有 $(k\in N\ \text{且有}\ p^k\le n)$

  于是问题继续转化:

  • 对于 $[2,n]$ 中的质数,
    每个质数可选择其任意次幂 (包括$0$次幂) ,
    并选择任意多个
    求其总和为 $n$ 的方案数

  考虑对 $0$ 次幂进行处理 :

  • 对于任何一种总和 $<n$ 的情况
    在添加若干 $1$ 后 , 都会变成 $n$

  • 所以考虑 忽略掉所有的 $1$
    将 求总和为 $n$ 的方案数变为:
    求 $\sum\limits_{i=1}^{n} \text{(总和为}i\text{的方案数)}$

• 最终转化结果:

  对于 $[2,n]$ 中的质数,
  每个质数可选择其任意非 $0$ 次幂 ,
  并选择任意多个
  求 $\sum\limits_{i=1}^{n} \text{(总和为}i\text{的方案数)}$

  变成了一个完全背包问题.
  也就是说,只要你会简单的完全背包
  就可以做出这么 Naive 神仙的题

附代码:

#include<cstdio>
#include<ctype.h>
const int MARX = 1010;
//=============================================================
int n,num , prime[MARX];
bool vis[MARX];
long long ans,f[MARX]={1}; 
//=============================================================
inline int read() 
{
    int s=1, w=0; char ch=getchar();
    for(; !isdigit(ch);ch=getchar()) if(ch=='-') s =-1;
    for(; isdigit(ch);ch=getchar()) w = w*10+ch-'0';
    return s*w;
}
void get_prime()//埃氏筛筛出<=n的素数
{
	for(int i=2;i<=n;i++)
	{
	  if(!vis[i]) prime[++num]=i;
	  for(int j=1;i*j<=n;j++) vis[i*j]=1;
	} 
}
void dp()//完全背包 
{
	for(int i=1;i<=num;i++)//将每个质数拿出,作为物品 
	  for(int k=n;k>=prime[i];k--)//枚举背包容量 
	    for(int mul=prime[i];mul<=k;mul*=prime[i])//枚举 
	      f[k]+=f[k-mul];
}
//=============================================================
signed main()
{
	n=read();
	get_prime();
	dp();
	for(int i=1;i<=n;i++) ans+=f[i];//获得各容量的方案数 
	printf("%lld",ans+1);//答案 = 总方案数 + 容量为0的方案 
}