cafelier@SRM

SRM508 500

22:32 |

class YetAnotherORProblem { public:
   map<vector<long long>, int> memo;
   int countSequences(const vector<long long>& R) 
   {
      // 全部 0 なら 1 通り
      if( count(R.begin(),R.end(),0) == R.size() )
         return 1;

      // メモ化
      if( memo.count(R) )
         return memo[R];

      // 足し算やOR算の結果の最下位ビットが0の場合の数
      // 最下位ビットなんてなかった、と思って数える
      vector<long long> RR;
      for(int i=0; i<R.size(); ++i)
         RR.push_back(R[i]>>1);

      int total = countSequences(RR);

      // 足し算やOR算の結果の最下位ビットが1の場合の数
      for(int i=0; i<R.size(); ++i)
         if( R[i] ) // A[i]の最下位ビットを1にする場合の数
         {
            if( (R[i]&1) == 0 ) RR[i]--; // 繰り下がり
            total = (total + countSequences(RR)) % 1000000009;
            if( (R[i]&1) == 0 ) RR[i]++;
         }

      // メモ化
      return memo[R] = total;
   }
};

• d段再帰した段階での R[i] として現れうる数値は
  • R[i] / 2^{d-1} または
  • R[i] / 2^{d-1} - 1
• のどっちかしかない（多分）ので、
• O( 2^len(R) * log(max(R)) ) 状態

• という「どっちかしかない」をフラグにすれば普通のDPになるのか。なるほど。