题目
为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下：
有一个数列A已知对于所有的(A[i])都是1~n的自然数，并且知道对于一些(A[i])不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和 (mod 1000000007)的值，是不是很简单呢？呵呵！
输入格式
第一行三个整数(n,m,k)分别表示数列元素的取值范围，数列元素个数，以及已知的限制条数。
接下来(k)行，每行两个正整数(x,y)表示(A[x])的值不能是(y)。
输出格式
一行一个整数表示所有可能的数列的积的和对(1000000007)取模后的结果。如果一个合法的数列都没有，答案输出(0)。
输入样例
3 4 5
1 1
1 1
2 2
2 3
4 3
输出样例
90
样例解释
(A[1])不能取1
(A[2])不能取2、3
(A[4])不能取3
所以可能的数列有以下12种
数列 积
2 1 1 1 2
2 1 1 2 4
2 1 2 1 4
2 1 2 2 8
2 1 3 1 6
2 1 3 2 12
3 1 1 1 3
3 1 1 2 6
3 1 2 1 6
3 1 2 2 12
3 1 3 1 9
3 1 3 2 18
数据范围
数据范围
30%的数据(n le 4,m le 10,k le 10)
另有20%的数据(k=0)
70%的数据(nle1000,mle 1000,kle 1000)
100%的数据(nle 109,mle 10^9,kle 10^5,1le yle n,1le xle m)
题解
若无限制, 每个位置都可以选择(1-n), 答案自然是
((1+2+3+4+5+dots+n)^m)
如果加入了限制, 第(x)位不能选(y), 那么答案就会减少其它位之积乘(y).
注意, 样例中存在(x,y)都相等的两次输入, 所以需要用map去重, 否则会多减
代码
#include <bits/stdc++.h>
using namespace std;
struct A {
int a, b;
bool operator>(A y) const { return (a != y.a) ? a > y.a : b > y.b;}
bool operator<(A y) const { return (a != y.a) ? a < y.a : b < y.b; }
};
const long long mod = 1e9 + 7;
long long n, m, k, sum[100010], ans, v;
int id, t, cnt;
map<int, int> ma;
map<A, bool> mb;
long long pow(long long x, long long y) {
long long tot = 1;
while (y) {
if (y & 1) tot = tot * x % mod;
x = x * x % mod;
y >>= 1;
}
return tot;
}
long long f2(long long x) { return pow(x % mod, mod - 2); }
long long f1(long long x, long long y) { return x % mod * f2(y) % mod; }
int main() {
scanf("%lld%lld%lld", &n, &m, &k);
ans = pow(n * (n + 1) / 2 % mod, m);
for (int i = 1; i <= k; i++) sum[i] = n * (n + 1) / 2;
for (int i = 1; i <= k; i++) {
scanf("%d%lld", &id, &v);
t = ma[id];
if (!t) t = ma[id] = ++cnt;
if (mb.count((A){t, (int)v})) continue;
mb[(A){t, (int)v}] = 1;
ans = (ans - f1(ans, sum[t]) * v % mod + mod) % mod;
sum[t] = (sum[t] - v + mod) % mod;
}
printf("%lld", ans);
return 0;
}