bzoj 1025: [SCOI2009]游戏

这道题可以转换一下。

试想每一个对应关系a-b为从a->b的一条边，

那么图中一定存在n条边且每个点入度出度都为1，

易证一定存在一个或几个环。

实际上排数就是这几个环大小的最小公倍数。

即求和为n的数列的最小公倍数种数。

那么可以直接DP

 1 /*
 2 ID:WULALA
 3 PROB:bzoj1025 
 4 LANG:C++
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <iostream>
11 #include <ctime>
12 #include <set>
13 #define N 1008
14 #define M
15 #define mod
16 #define mid(l,r) ((l+r) >> 1)
17 #define INF 0x7ffffff
18 using namespace std;
19 
20 int p[N],tot,n;
21 long long f[2][N],sum;
22 
23 void find_prime()
24 {
25     bool vis[N];
26     memset(vis,false,sizeof(vis));
27     for (int i = 2;i <= n;i++)
28         if (!vis[i])
29         {
30             p[++tot] = i;
31             for (int j = i;j <= n;j+=i) vis[j] = true;
32         }
33 }
34 
35 void init()
36 {
37     scanf("%d",&n);
38     find_prime();
39     f[0][0] = 1;
40 }
41 
42 void work()
43 {
44     for (int i = 1;i <= tot;i++)
45     {
46         for (int j = 0;j <= n;j++) f[i&1][j] = f[!(i&1)][j];
47         for (int j = p[i];j <= n;j*=p[i])
48             for (int k = 0;k <= n-j;k++) f[i&1][k+j] += f[!(i&1)][k];
49     }
50     for (int i = 0;i <= n;i++) sum += f[tot&1][i];
51 }
52 
53 int main()
54 {
55     init();
56     work();
57     printf("%lld
",sum);
58     return 0;
59 }

View Code