【做题】TCSRM601 Div1 500 WinterAndSnowmen——按位考虑&dp

标签：暴力   技巧   mat   const   div   不同   register   csr   using   

原文链接https://www.cnblogs.com/cly-none

题意：求有多少对集合\(S,T\)满足：\(S \subseteq \{1,2...n \}, T \subseteq \{1,2...m\},S \bigcap T = \emptyset\)，且\(S\)中所有元素的异或和小于\(T\)中所有元素的异或和。对\(10^9+7\)取模。

\(n,m \leq 2000\)

首先，通过记录当前两个集合的异或和，转移时考虑每个元素的3种选择，容易得到\(O(n^3)\)的暴力dp。然而，要对此优化却是一件困难的事情。

但无论如何，对状态的优化的必要的。因此，我们就必须避免同时记录两个集合的异或和。考虑两个异或和如果只有一位，那么它们的大小关系就能通过记录一位来得到。而对于多位的二进制数的大小比较，我们也只用比较不同的最高位就可以了。

因此，我们枚举不同的最高位。那么，我们就可以忽略后面的位，并只用记录我们所枚举的这一位。剩下的问题就在于保证更高的位是相等的。那可以用记录两个数在更高位上的异或和实现，异或和为0，这两个数就是相等的。

时间复杂度\(O(n^2\log n)\)。

#include 
using namespace std;

const int N = 2060, MOD = (int)(1e9 + 7);
int dp[N][N][2],n,m,len,ans;

class WinterAndSnowmen {
public:
  int getNumber( int N, int M );
};
int WinterAndSnowmen::getNumber(int N, int M) {
  n = N, m = M;
  len = max(n,m);
  for (int s = 1 ; s >(s-1))][k] += dp[i-1][j][k]) %= MOD;
          if (i >(s-1))][k ^ ((i >> (s-1))&1)] += dp[i-1][j][k]) %= MOD;
          (dp[i][j][k] += dp[i-1][j][k]) %= MOD;
        }
      }
    }
    (ans += dp[len][1][1]) %= MOD;
  }
  return ans;
}

小结：虽然是“思维训练”中的题，但也会有自己没有掌握的技巧。

【做题】TCSRM601 Div1 500 WinterAndSnowmen——按位考虑&dp

标签：暴力   技巧   mat   const   div   不同   register   csr   using   

原文地址：https://www.cnblogs.com/cly-none/p/9695526.html