“玲珑杯”ACM比赛 Round #4 E -- array DP-白红宇

“玲珑杯”ACM比赛 Round #4 E -- array DP

阅读量：5215 次

发布时间：2019-06-14

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

DP[val]表示以val这个值结尾的等差数列有多少个

DP[val] += DP[val / 2];

数值很大，用map<int, int>DP即可。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 const int maxn = 1e5 + 20;set
                 
                  ss;map
                  
                   dp;const int MOD = 1e9 + 7;void work() { ss.clear(); dp.clear(); int n; cin >> n; for (int i = 1; i <= n; ++i) { int x; cin >> x; if (x == 1) { ss.insert(x); dp[1]++; } else { if (x & 1) continue; ss.insert(x); dp[x] += dp[x / 2]; dp[x] %= MOD; } } int ans = 0; for (set
                   
                     :: iterator it = ss.begin(); it != ss.end(); ++it) { int t = *it; if (t == 1) { ans += dp[t]; ans %= MOD; } else { if (t & 1) continue; ans += dp[t]; ans %= MOD; } } cout << ans << endl;}int main() {#ifdef local freopen("data.txt","r",stdin);#endif IOS; int t; cin >> t; while (t--) work(); return 0;}