BZOJ2751 [HAOI2012] 容易题(easy)

2018 年 03 月 14 日发布.

Description

一个长为$m$的序列，每个数是$0$到$n$；还有$k$个限制:$A_x \neq y$；求所有可能序列的乘积的和。

Solution

和题目标题一样==。注意判重。

Code

#include <algorithm>
#include <cstdio>
#include <map>
#include <set>
typedef long long LL;
const int mod = 1000000007;
std::map<int, int> M;
std::map<int, std::set<int> > MS;
int main() {
  int n, m, k, x, y;
  scanf("%d%d%d", &n, &m, &k);
  n = (LL)n * (n + 1) / 2 % mod;
  while (k--) {
    scanf("%d%d", &x, &y);
    if (!M.count(x)) {
      M[x] = n;
      MS[x] = std::set<int>();
    }
    if (!MS[x].count(y)) {
      (M[x] -= y) %= mod;
      MS[x].insert(y);
    }
  }
  int ans = 1;
  m -= M.size();
  for (; m; m >>= 1, n = (LL)n * n % mod)
    if (m & 1) ans = (LL)ans * n % mod;
  for (std::map<int, int>::iterator it = M.begin(); it != M.end(); ++it)
    ans = (LL)ans * it->second % mod;
  printf("%d\n", (ans + mod) % mod);
  return 0;
}