【容斥】【P6521】 [CEOI2010 day2] pin

Analysis

因为做这个题的时候，憨憨 @ShineEternal 翻译错了题面，把恰好不同译成了恰好相同，所以我按照相同做的，当然没有什么区别，把 $d$ 改成 $4 - d$ 即可。因此下面考虑恰好有 $d$ 个位置相同应该怎么做。

首先我们可以用 map 轻松维护出与当前字符串至少某几个位置相同的字符串个数（只需要把剩下的位置都统一改成某个无关字符即可）。

考虑容斥计算答案。设与当前字符串至少 $i$ 个位置相同的统计值为 $f_i$，恰好有 $i$ 个位置相同的实际值为 $g_i$。

因为没有重复的字符串，所以 $g_3 = f_3$。

考虑计算 $g_2$。任何一个有三个位置相同的字符串都被统计了 $C_{3}^2$ 次，因此 $g_2 = f_2 - G_{3}^2 g_3$。

类似的，可以得到 $g_i = f_i - \sum\limits_{j = i + 1}^3 C_j^i g_j$。递推出 $g_d$ 即可。

Code

#include <map>
#include <vector>
#include <string>
#include <iostream>

int n, d, dd;
long long C[5][5], g[5];
long long ans;
std::string s, t;
std::vector<int> sta[5];
std::map<std::string, int> mp;

void calc(const int x) {
  for (int i = 3; i >= dd; --i) {
    long long f = 0;
    for (auto u : sta[i]) {
      t = s;
      for (int o = 0; o < 4; ++o) if ((u & (1 << o)) == 0) {
        t[o] = '$';
      }
      f += mp[t];
    }
    for (int j = i + 1; j <= 3; ++j) {
      f -= C[j][i] * g[j];
    }
    g[i] = f;
  }
  ans += g[d];
}

void add() {
  for (int i = 0; i < 4; ++i) {
    for (auto u : sta[i]) {
      t = s;
      for (int o = 0; o < 4; ++o) if ((u & (1 << o)) == 0) {
        t[o] = '$';
      }
      ++mp[t];
    }
  }
}

inline int countbit(const int x) { return __builtin_popcount(x); }

int main() {
  std::cin >> n >> d;
  C[0][0] = 1;
  for (int i = 1; i <= 3; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
  }
  dd = d = 4 - d;
  for (int i = 0, upc = 1 << 4; i < upc; ++i) {
    sta[countbit(i)].push_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    std::cin >> s;
    calc(i);
    add();
  }
  std::cout << ans << std::endl;
}