数论+DP HDOJ 4345 Permutation-白红宇

数论+DP HDOJ 4345 Permutation

阅读量：7045 次

发布时间：2019-06-28

本文共 1817 字，大约阅读时间需要 6 分钟。

题意：一个置换群，经过最少k次置换后还原。问给一个N个元素，在所有的置换群里，有多少个不同的k。

分析：这道题可以转化成：N =

/************************************************* Author        :Running_Time* Created Time  :2015-8-27 18:11:40* File Name     :F.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e3 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int prime[N/2];bool is_prime[N];ll dp[200][N];int seive(void) { int p = 0; memset (is_prime, true, sizeof (is_prime)); for (int i=2; i<=1000; ++i) { if (is_prime[i]) prime[++p] = i; for (int j=1; j<=p && prime[j]*i<=1000; ++j) { is_prime[i*prime[j]] = false; if (i % prime[j] == 0) break; } } return p;}int main(void) { int p = seive (); int n, m = 0; while (scanf ("%d", &n) == 1) { memset (dp, 0, sizeof (dp)); dp[0][0] = 1; for (int i=1; i<=p; ++i) { for (int j=0; j<=n; ++j) dp[i][j] = dp[i-1][j]; int res = prime[i]; if (res <= n) m = i; else break; while (res <= n) { for (int j=0; j+res<=n; ++j) { if (dp[i-1][j]) dp[i][j+res] += dp[i-1][j]; } res *= prime[i]; } } ll ans = 0; for (int i=1; i<=n; ++i) ans += dp[m][i]; printf ("%I64d\n", ans + 1); } return 0;}