首页 > 代码库 > BZOJ 1025 游戏
BZOJ 1025 游戏
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 。
Source
首先，我们可以这样思考，每个置换排列都有若干个循环结。e.g. 3 2 1 5 4 6的循环结就是(1,2,3)(4,5)(6)，所以它所能变换的排列数为(lcm为最小公倍数)lcm(1,2,3)=6。而1+2+3=6。
所以我们只需要求出满足x1+x2+x3+x4+...xm=n，lcm(x1,x2,x3,...,xm)有多少种。
蒟蒻的我也只能YY到这里了，暴力枚举肯定没戏，剩下的是题解做的了，其实想想应该是能自己策清的。
首先我们令x1+x2+x3+...+xm<=n(如果少了我们可以补1嘛)。再令x1=p1^t1,x2=p2^t2...其中pi为质数且pi≠pj(i≠j)，则lcm=∏xi，明显不重复。
然后，我们只需要证明若xi=pi*pj，也可以用lcm也包含在上面的情况。
不妨设pi<pj，则因为p是质数，明显有pi*pj>pi+pj，所以对于这种情况我们在pi,pj的情况中枚举了(少了仍然可以补1)。
因此，我们可以dp了，哈哈哈。
f[i][j]表示前i个质数，何为j的方案数(我们都是拆分成pi^ti的形式，刚刚已经证明了其不可能重复，也包含了所有方案)。转移自己脑补一下吧！！！
1 #include<cstdio> 2 #include<cstdlib> 3 using namespace std; 4 5 #define maxn 1010 6 int n,tot,prime[maxn]; long long f[maxn][maxn],ans; bool exist[maxn]; 7 8 inline void find() 9 {10 for (int i = 2;i <= n;++i)11 if (!exist[i])12 {13 prime[++tot] = i;14 for (int j = i*i;j <= n;j += i) exist[j] = true;15 }16 }17 18 inline void dp()19 {20 f[0][0] = 1;21 for (int i = 1;i <= tot;++i)22 {23 for (int j = 0;j <= n;++j) f[i][j] = f[i-1][j];24 for (int j = prime[i];j <= n;j *= prime[i])25 {26 for (int k = 0;k + j <= n;++k)27 f[i][k+j] += f[i-1][k];28 }29 }30 for (int i = 0;i <= n;++i) ans += f[tot][i];31 }32 33 int main()34 {35 freopen("1025.in","r",stdin);36 freopen("1025.out","w",stdout);37 scanf("%d",&n);38 find();39 dp();40 printf("%lld",ans);41 fclose(stdin); fclose(stdout);42 return 0;43 }
BZOJ 1025 游戏