SRM 572 D2L3：DistinctRemainders，dp，math - c++编程基础

题目：http://community.topcoder.com/stat c=problem_statement&pm=12384&rd=15492

参考：http://apps.topcoder.com/wiki/display/tc/SRM+572

把数学部分搞定之后dp比较简单，关键是找到所取数的模集与最终序列种数的关系。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                 #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         using namespace std; #define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC) typedef pair
                        
                          pii; typedef long long llong; typedef pair
                         
                           pll; #define mkp make_pair /*************** Program Begin **********************/ const int MOD = 1e9 + 7; long long dp[51][51][2501]; class DistinctRemainders { public: long long N; int M; int rec(int cur, int K, int q) { long long & res = dp[cur][K][q]; if (res != -1) { return res; } if (M == cur) { // base cases if (q % M == N % M) { long long Q = (N - q) / M; res = K; // C(Q + K - 1, K - 1) * K! for (int i = 0; i < K - 1; i++) { res *= ( (Q + K - 1 - i) % MOD ); res %= MOD; } return res; } else { res = 0; return res; } } res = 0; // add res += rec(cur + 1, K + 1, q + cur); res %= MOD; // ignore res += rec(cur + 1, K, q); res %= MOD; return (int)res; } int howMany(long long N, int M) { int res = 0; this->N = N; this->M = M; memset(dp, -1, sizeof(dp)); res = rec(0, 0, 0); return res; } }; /************** Program End ************************/