题解 P4161 【[SCOI2009]游戏】

灵乌路空 · 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的方案 
}