DP(优化) UVALive 6073 Math Magic-白红宇

DP(优化) UVALive 6073 Math Magic

阅读量：7103 次

发布时间：2019-06-28

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

/************************************************* Author        :Running_Time* Created Time  :2015/10/28 星期三 20:20:09* File Name     :H.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 M = 1e2 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-10;const double PI = acos (-1.0);int dp[2][N][N];int lcm[N][N];int vec[N];int GCD(int a, int b) { return b ? GCD (b, a % b) : a;}void init(void) { for (int i=1; i<=1000; ++i) { for (int j=1; j<=1000; ++j) { lcm[i][j] = i * j / GCD (i, j); } }}inline void add(int &x, int y) { x += y; if (x > MOD) x -= MOD;}int main(void) { init (); int n, m, k; while (scanf ("%d%d%d", &n, &m, &k) == 3) { int t = 0; for (int i=1; i<=m; ++i) { if (m % i == 0) vec[t++] = i; } int now = 0; for (int i=0; i<=n; ++i) { for (int j=0; j
                      
                        n || m % y != 0) continue; dp[now][x][y] = (dp[now][x][y] + dp[now^1][i][vec[j]]) % MOD; } } } } printf ("%d\n", dp[now][n][m]); } //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;}