题解 P4161 【[SCOI2009]游戏】

先无良宣传一下博客 \(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的方案 
}

上一篇:$SCOI2009\ $windy数 数位$dp$


下一篇:P4161 [SCOI2009]游戏 素数筛 + 背包DP