HDU 4028 The time of a day（11年上海 離散化DP）

題目：給出1-N這N個數，問有多少個子集，集合裡的lcm是大於等於m的

可以發現m的范圍是很大的，而且1-N的子集也是很多的2^N-1個。

覺得會是DP，但是由於數據范圍太大，而無從下手。

其實可以發現的是雖然子集很多，但是LCM的值沒有那麼多，所以可以用map保存i-1個數的時候時的所有lcm值

這樣就可以轉移了

map<LL,LL>dp[i]。表示i個數，可以有it->second種情況組成it->first。

[cpp]
#include<iostream>  
#include<cstdio>  
#include<map>  
#include<cstring>  
#include<cmath>  
#include<vector>  
#include<queue>  
#include<algorithm>  
#include<set>  
#define inf 110000  
#define M 10005  
#define N 10005  
#define Min(a,b) ((a)<(b)?(a):(b))  
#define Max(a,b) ((a)>(b)?(a):(b))  
#define pb(a) push_back(a)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define eps 1e-9  
#define zero(a) fabs(a)<eps  
#define LL long long  
#define MOD 1000000007  
using namespace std; 
map<LL,LL>dp[45]; 
map<LL,LL>::iterator it; 
LL gcd(LL a,LL b){ 
    return b==0?a:gcd(b,a%b); 
} 
LL lcm(LL a,LL b){ 
    return a/gcd(a,b)*b; 
} 
void DP(){ 
    dp[1][1]=1; 
    for(int i=2;i<=40;i++){ 
        dp[i]=dp[i-1];   //不取第i個數的所有情況，先復制過來  
        dp[i][i]++;      //只取第i個數，不能落下  
        for(it=dp[i-1].begin();it!=dp[i-1].end();it++) 
            dp[i][lcm(i,it->first)]+=it->second;   //然後考慮在前i-1個數的基礎上加入第i個數  
    } 
} 
LL n,m; 
int main(){ 
    DP(); 
    int t,cas=0; 
    scanf("%d",&t); 
    while(t--){ 
        scanf("%I64d%I64d",&n,&m); 
        LL ans=0; 
        //遍歷一遍  
        for(it=dp[n].begin();it!=dp[n].end();it++) 
            if(it->first>=m)  
                ans+=it->second; 
        printf("Case #%d: %I64d\n",++cas,ans); 
    } 
    return  0; 
} 

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#define inf 110000
#define M 10005
#define N 10005
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define eps 1e-9
#define zero(a) fabs(a)<eps
#define LL long long
#define MOD 1000000007
using namespace std;
map<LL,LL>dp[45];
map<LL,LL>::iterator it;
LL gcd(LL a,LL b){
 return b==0?a:gcd(b,a%b);
}
LL lcm(LL a,LL b){
 return a/gcd(a,b)*b;
}
void DP(){
 dp[1][1]=1;
 for(int i=2;i<=40;i++){
  dp[i]=dp[i-1];   //不取第i個數的所有情況，先復制過來
  dp[i][i]++;      //只取第i個數，不能落下
  for(it=dp[i-1].begin();it!=dp[i-1].end();it++)
   dp[i][lcm(i,it->first)]+=it->second;   //然後考慮在前i-1個數的基礎上加入第i個數
 }
}
LL n,m;
int main(){
 DP();
 int t,cas=0;
 scanf("%d",&t);
 while(t--){
  scanf("%I64d%I64d",&n,&m);
  LL ans=0;
  //遍歷一遍
  for(it=dp[n].begin();it!=dp[n].end();it++)
   if(it->first>=m)
    ans+=it->second;
  printf("Case #%d: %I64d\n",++cas,ans);
 }
 return  0;
}