ZOJ 3662 Math Magic (2012 Changchun Regional; LCM,DP)

제목 설명: K의 수를 제시하여 이 K의 수를 N으로 하고 LCM을 M으로 하며 몇 가지가 있느냐고 묻는다.누드DP아...T는 dp[i][j][k]를 설정하여 i개수와 j, LCM이 k일 때의 종수를 나타낸다.이렇게 하면 dp[100][1000][1000]을 켜려면 최적화가 필요하다.우선 1차원에서 우리는 롤러 그룹으로 최적화할 수 있다.그 다음,
LCM이 M이기 때문에 중간 상태의 LCM은 틀림없이 M의 약수이고 가입한 수도 틀림없이 M의 약수이기 때문에 우리는 LCM의 약수를 미리 처리한다.
그러면 LCM과Ai는 그 약수일 뿐이다. 이렇게 하면 3차원에서 40까지 잘라낼 수 있다.마지막으로 dp[2][1000][40]를 켜면 충분해요.복잡성: O(100*1000*32*32)(열거 K 개수* 현재 및 * 열거 현재 수의 값* 열거 LCM)


#include 
 
   
    
  
#include 
  
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
            #include 
            
              #include 
             
               #include 
              
                #define MID(x,y) ((x+y)>>1) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int dp[2][1010][40]; int LCM[1010][1010]; bool tmp_ok[1000]; int N, M, K; const int MOD = 1000000007; vector 
               
                 divisor; int pos[1010]; int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } int lcm(int a, int b){ return a / gcd(a,b) * b; } void get_divisor(int num){ mem(pos, -1); divisor.clear(); for (int i = 1; i <= num; i ++){ if (num % i == 0){ divisor.push_back(i); pos[i] = divisor.size() - 1; } } return ; } int main(){ mem(LCM, 0); for (int i = 1; i <= 1000; i ++) for (int j = 1; j <= 1000; j ++) LCM[i][j] = lcm(i, j); while(scanf("%d%d%d", &N, &M, &K) == 3){ get_divisor(M); mem(dp, 0); dp[0][0][0] = 1; for (int i = 1; i <= K; i ++){ mem(dp[i&1], 0); for (int j = 0; j <= N; j ++){ for (int p = 0; p < (int)divisor.size(); p ++){ //int tmp1 = divisor[p]; if (j + divisor[p] <= N){ for (int l = 0; l < (int)divisor.size(); l ++){ //int tmp2 = divisor[l]; if (dp[(i+1)&1][j][l] != 0){ int new_l = LCM[divisor[p]][divisor[l]]; if (new_l > M) break; new_l = pos[new_l]; dp[i&1][j+divisor[p]][new_l] += dp[(i+1)&1][j][l]; if (dp[i&1][j+divisor[p]][new_l] >= MOD) dp[i&1][j+divisor[p]][new_l] -= MOD; } } } } } } printf("%d
", dp[K&1][N][pos[M]]); } return 0; }

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

B God Create Math 사고방식

B.God Create Math There is a saying: computer was the crystallizationof men' intelligence, but math is fromgod. Today, ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

ZOJ 3662 Math Magic (2012 Changchun Regional; LCM,DP)

좋은 웹페이지 즐겨찾기