【訓練題40：高維字首和】Counting Good Teams | Gym - 101484K

題意

• Counting Good Teams | Gym - 101484K

  有 n n n 個人， m m m 個課。每個人有一個擅長科目的集合 S i ∈ [ 0 , 2 m ) S_i\in[0,2^m) Si​∈[0,2m)

  你要選擇一個兩個人的隊伍，使得這兩個人每個人都至少有一門科目是他會的但是對方不會的。

  問選擇的方案數。

範圍

• 2 ≤ n ≤ 1 0 5 2\le n\le 10^5 2≤n≤105

  2 ≤ m ≤ 21 2\le m\le21 2≤m≤21

思路

• 正面枚舉不好做，我們考慮反面情況，就是這兩個人會的領域，其中一個人是另一個人的子集。

  設 d p [ S ] dp[S] dp[S] 表示會的領域為 S S S 的情況下，子集的數目。

  則根據定義， d p [ S ] = ∑ T ⊂ S d p [ T ] dp[S]=\sum_{T\sub S}dp[T] dp[S]=∑T⊂S​dp[T]

  但是我們暴力枚舉子集的子集，時間複雜度為 O ( 3 n ) O(3^n) O(3n) (為什麼，可以作為課後習題)

  但是我們有更優的政策來達到 O ( n × 2 n ) O(n\times2^n) O(n×2n)

• 字首和

  三維字首和，我們可能會這麼寫

for i = 1 to n
	for j = 1 to n
		for k = 1 to n
			dp[i][j][k] += dp[i-1][j][k]
for i = 1 to n
	for j = 1 to n
		for k = 1 to n
			dp[i][j][k] += dp[i][j-1][k]
for i = 1 to n
	for j = 1 to n
		for k = 1 to n
			dp[i][j][k] += dp[i][j][k-1]
           

• 高維字首和，求子集 d p dp dp 則可以變成這樣：

for i = 1 to n
	for j = 0 to (1<<n)-1
		if(j & (1<<i))
			dp[j] += dp[j ^ (1<<i)]
           

• 高維字首和，求超集 d p dp dp 則可以變成這樣：

for i = 1 to n
	for j = 0 to (1<<n)-1
		if(!(j & (1<<i)))
			dp[j] += dp[j | (1<<i)]
           

• 那麼，我們對于某一個狀态 S S S，直接就能得到有多少個狀态 T T T，滿足 T ⊂ S T\sub S T⊂S

  考慮答案，就是 n ∗ ( n − 1 ) / 2 n * (n - 1) / 2 n∗(n−1)/2 再減掉非法的方案。有哪些非法的方案？

  （1）集合 S S S 的個數有 c n t [ S ] cnt[S] cnt[S] 個，集合 S S S 的子集個數有 d p [ S ] dp[S] dp[S] 個

  那麼集合 S S S 的真子集的個數有 d p [ S ] − c n t [ S ] dp[S]-cnt[S] dp[S]−cnt[S] 個。

  那麼減掉的數量就是 c n t [ S ] × ( d p [ S ] − c n t [ S ] ) cnt[S]\times(dp[S]-cnt[S]) cnt[S]×(dp[S]−cnt[S])

  （2）集合 S S S 和集合 S S S 的人的配對也是非法的。

  那麼減掉的數量就是 c n t [ S ] × ( c n t [ S ] − 1 ) / 2 cnt[S]\times(cnt[S]-1)/2 cnt[S]×(cnt[S]−1)/2

代碼

• 時間複雜度： O ( m × 2 m ) O(m\times 2^m) O(m×2m)

ll cnt[MAX];
ll dp[MAX];

int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i){
        int t;
        scanf("%d",&t);
        cnt[t]++;
        dp[t]++;
    }
    for(int i = 0;i < m;++i)
    for(int j = 0;j < (1<<m);++j)
    if(j & (1<<i))
        dp[j] += dp[j^(1<<i)];
    ll ans = (ll)n * (n - 1) / 2;
    for(int i = 0;i < (1<<m);++i){
        ans -= cnt[i] * (dp[i] - cnt[i]);
        ans -= cnt[i] * (cnt[i] - 1) / 2;
    }
    printf("%lld",ans);
    return 0;
}