Description
There is an arrangement of N numbers and a permutation relation that alter one arrangement into another.
For example, when N equals to 6 the arrangement is 123456 at first. The replacement relation is 312546 (indicate 1->2, 2->3, 3->1, 4->5, 5->4, 6->6, the relation is also an arrangement distinctly).
After the first permutation, the arrangement will be 312546. And then it will be 231456.
In this permutation relation (312546), the arrangement will be altered into the order 312546, 231456, 123546, 312456, 231546 and it will always go back to the beginning, so the length of the loop section of this permutation relation equals to 6.
Your task is to calculate how many kinds of the length of this loop section in any permutation relations.
Output
For each test case, output only one integer indicates the amount the length of the loop section in any permutation relations.
题目大意：给你一个数N。代表123456......N一串这样的数字序列。
你可以指定任意位移操作，问你这个串循环出现的周期可能是多少呢？
这个题目一看一点想法都没有呢。后来看过网上神牛们写的博客和题解后才知道这是个数学题先把它转化为数学问题，再DP完美解决呢。
下面上我的代码，参考神牛写的哦。
＃i nclude <cstdio>
#define ll long long
#define maxn 1010
using namespace std;
ll f[maxn][maxn],a[maxn],tot=0;
bool b[maxn];
void getprim()//求得1010范围内的质数
{
for (int i=2; i<maxn; i++)
{
if (!b[i])
{
a[++tot]=i;
for (int j=i; j<maxn; j+=i) b[j]=true;
}
}
}
int main()
{
getprim();
f[0][0]=1;//DP初始启动条件
for (int i=1; i<=tot; i++)//没有考虑有1加在里面
{
for (int j=0; j<maxn; j++) f[i][j]=f[i-1][j];
int now=a[i];
while (now<maxn)
{
for (int j=0; j+now<maxn; j++)
f[i][j+now]+=f[i-1][j];
now*=a[i];
}
}
ll n,ans;
while (scanf("%I64d",&n)!=EOF)
{
ans=0;
for (int i=1; i<=n; i++)
ans+=f[tot][i];//构成比n小的任意一个数都行，因为后面可以被1填充
printf("%I64d\n",ans+1);//没有考虑全部都是1的情况，故要加上去
}
return 0;
}
题目的解法也有记忆化搜索版本的，不过我这个代码已经是0MS飘过了哦 ^_^
