DP/整数拆分
整个映射关系可以分解成几个循环（置换群的预备知识？），那么总行数就等于各个循环长度的最小公倍数+1（因为有个第一行的1~N）。那么有多少种可能的排数就等于问有多少种可能的最小公倍数。
呃现在问题就变成了：给你一个数N，将它分解成几个数的和，然后找这些数的最小公倍数总共多少种。很明显又要找质数了>_>。
可以发现只要找循环长度（即拆出来的数）是质数的幂的情况就可以了，因为像6=2*3这种情况，我们可以用2和3来代替，又由于对于正整数来说，和$\leq$积，所以所有的非质数幂的情况都可以用质数幂的情况来表示/代替。（取一个6等于取2和3）
这个枚举总共有多少种分拆方案……我是用DP来实现的（没办法，dfs会TLE）
令$f[i][j]$表示用前 i 种质数的幂拼出 j 的方案数，那么$ans=\sum_{j=1}^n f[tot][j]$ tot为小于等于n的质数的数量。
转移也很简单啦~我的方法是从当前节点去更新其他节点的递推……写的可能有点奇怪……
f[i][j]可以转移到：f[i+1][j]和f[i+1][j+k] $(k=prime[i+1]^t)$ 呃……好像说的不太清楚……看我代码吧>_<不过我开了滚动数组……
/**************************************************************
Problem: 1025
User: Tunix
Language: C++
Result: Accepted
Time:20 ms
Memory:828 kb
****************************************************************/ //BZOJ 1025
#include<cstdio>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;++i)
using namespace std;
typedef long long LL;
const int N=;
int n,prime[N],tot;
LL f[][N],ans;
bool vis[N];
void getprime(int n){
F(i,,n){
if (!vis[i]) prime[++tot]=i;
F(j,,tot){
if (i*prime[j]>n) break;
vis[i*prime[j]]=;
if (i%prime[j]==) break;
}
}
}
int main(){
scanf("%d",&n);
getprime(n);
f[][]=;
for(int i=;i<tot;i++){
int now=i&;
F(j,,n) f[now^][j]=;
F(j,,n){
f[now^][j]+=f[now][j];
for(int k=prime[i+];k+j<=n;k*=prime[i+])
f[now^][j+k]+=f[now][j];
}
}
F(j,,n) ans+=f[tot&][j];
printf("%lld\n",ans+);
return ;
}
P.S.我一开始想的其实是$ans=\sum_{i=1}^{tot} \sum_{j=1}^n f[i][j]$ 所以转移的时候就不是从f[i]转移到f[i+1]了……而是转移到所有的$f[t][j+k](t>i)$所以时间复杂度更高，后来写题解的时候才突然想到这个更好理解&好写的代码……
/**************************************************************
Problem: 1025
User: Tunix
Language: C++
Result: Accepted
Time:368 ms
Memory:4796 kb
****************************************************************/ //BZOJ 1025
#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
using namespace std;
typedef long long LL;
const int N=;
int n,prime[N],tot,f[N][N];
LL ans;
bool vis[N];
void getprime(int n){
F(i,,n){
if (!vis[i]) prime[++tot]=i;
F(j,,tot){
if (i*prime[j]>n) break;
vis[i*prime[j]]=;
if (i%prime[j]==) break;
}
}
}
int main(){
scanf("%d",&n);
getprime(n);
f[][]=;
rep(i,tot) F(j,,n){
F(t,i+,tot)
for(int k=prime[t];j+k<=n;k*=prime[t])
f[t][j+k]+=f[i][j];
}
F(i,,tot) F(j,,n) ans+=f[i][j];
printf("%lld\n",ans+);
return ;
}
(一开始的奇怪做法)
1025: [SCOI2009]游戏
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1436 Solved: 900
[Submit][Status][Discuss]
Description
windy
学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排在纸上。然后再
在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，……，N。 如： 1 2 3 4 5
6 对应的关系为 1->2 2->3 3->1 4->5 5->4 6->6 windy的操作如下 1 2
3 4 5 6 2 3 1 5 4 6 3 1 2 4 5 6 1 2 3 5 4 6 2 3 1 4 5 6 3 1 2 5 4 6 1 2
3 4 5 6 这时，我们就有若干排1到N的排列，上例中有7排。现在windy想知道，对于所有可能的对应关系，有多少种可能的排数。
Input
包含一个整数，N。
Output
包含一个整数，可能的排数。
Sample Input
3
【输入样例二】
10
Sample Output
3
【输出样例二】
16
HINT
【数据规模和约定】
100%的数据，满足 1 <= N <= 1000 。