[bzoj] 1025: [SCOI2009]游戏

发表于   |   分类于   |  

题意

对于一些长度为n的排列，将其作为一个置换，
那么可能有一个自置换的次数使其回到1,2,3,…,n的情况。
求对于所有能够回到1,2,3..,n的排列，不同的次数共有多少种。

传送门

分析

移步守望、御神木的题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

inline void reads(int& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

typedef long long ll ;

#define  maxn  1010LL

int n , p , pri[maxn] = {0} ;
bool cps[maxn] = {0} ;
ll f[maxn][maxn] = {0} ;

int i , j ;

inline void GetPri() {
truepri[0] = 0 ;
truefor (i = 2 ; i <= n ; i ++ )
truetrueif (!cps[i]) {
truetruetruepri[++pri[0]] = i ;
truetruetruefor (j = i<<1 ; j <= n ; j += i )
truetruetruetruecps[j] = true ;
truetrue}
}

inline void dp() {
truefor (i = 0 ; i <= n ; i ++ )
truetruef[i][0] = 1 , f[0][i] = 1 ;
truefor (i = 1 ; i <= n ; i ++ )
truetruefor (j = 1 ; j <= pri[0] ; j ++ ) {
truetruetruef[i][j] = f[i][j-1] ;
truetruetruep = pri[j] ;
truetruetruewhile (i-p >= 0)
truetruetruetruef[i][j] += f[i-p][j-1] , p *= pri[j] ;
truetrue}
trueprintf("%lld\n", f[n][pri[0]]) ;
}

int main() {
//	#define READ
true#ifdef  READ
truetruefreopen(".in" ,"r",stdin ) ;
truetruefreopen(".out","w",stdout) ;
true#endif
trueread(n) ;
trueGetPri() ;
truedp() ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章