https://atcoder.jp/contests/abc172/tasks
E - NEQ
题意：要求构造两个长度为n的数列A，B，满足每个数列内部都不相等，且两个数列间对位不相等，即 A[i]=B[i]，且每个数大于0，小于等于m。问有多少种构造方式。
容斥
先构造出两个内部不相等的数列，构造方式就是1到m中选n个数全排列。
再把有对位重复的去掉，对于至少 i 位重复的情况，先从n位里选出 i 位，再给这 i 位分配数字，其它位还是全排列。
由于这过程中都满足内部不相等，所以直接容斥后结果就是答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
ll fac[N], inv[N];
ll power(ll a, int x) {
ll ans = 1;
while (x) {
if (x & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
x >>= 1;
}
return ans;
}
void init() {
fac[0] = 1;
for (int i = 1; i < N; i++) {
fac[i] = fac[i - 1] * i %mod;
}
inv[N - 1] = power(fac[N - 1], mod - 2);
for (int i = N - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % mod;
}
}
int n, m;
ll P(int n, int k) {
return fac[n] * inv[n - k] % mod;
}
ll C(int n, int k) {
return fac[n] * inv[n - k] % mod*inv[k] % mod;
}
int main() {
scanf("%d%d", &n, &m);
init();
ll ans = P(m, n)*P(m, n) % mod;
for (int i = 1; i <= n; i++) {
ll tmp = C(n, i)*P(m, i) % mod*P(m - i, n - i) % mod*P(m - i, n - i) % mod;
if (i & 1)ans = (ans - tmp + mod) % mod;
else ans = (ans + tmp) % mod;
}
printf("%lld\n", ans);
return 0;
}
|
F - Unfair Nim
题意：有n堆石子，两个人轮流从任意一堆拿任意个，先拿完的人赢。在比赛前，后手从第一堆中拿一些放到第二堆，使得后手赢。拿的个数大于等于0，小于第一堆石子数，问至少拿几个。
尼姆游戏，问题可以直接转化为 (a[1]−x)⨁(a[2]+x)=a[3]⨁⋯⨁a[n]，求最小的 x。
如果把 x 视为拿完后 第一堆剩下的石子数，则还可以进一步变为
maxmizes.t.xx+y=a[1]+a[2]=sx⨁y=a[3]⨁⋯⨁a[n]=k0<x≤a[1]
已知了 s 和 k，且由于每次进位最多进1，所以就可以分类讨论了。
对于每一位，如果 x+y=0,x⨁y=0，则低位一定不能进位，且当前位可能为 x,y 都为 0，或 x,y 都为 1，若都为 1，则当前位可以向高位进位。
类似的，对于其它三种情况，也可以得出 低位是否进位，当前位是否可以向高位进位，当前位的 x,y 可能都是0/都是1/一个0一个1。
再从最高位开始遍历，记录当前位是否需要向高位进位，如果需要进位，而 s，t 的情况不能进位，则gg。否则记录x，y中这一位有几个1。
最后再从高到低遍历一遍，如果这一位需要2个1，则 x 和 y 必定都是1；如果需要0个1，则都是0；如果需要1个1，则要尽量加在 x 上，所以贪心地能加就加。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n;
ll a[N], k;
ll ans;
int nd = 0, cnt[100];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
for (int i = 3; i <= n; i++)k ^= a[i];
ll s = a[1] + a[2];
for (int i = 50; i >= 0; i--) {
int x = (s >> i & 1), y = (k >> i & 1);
if (x == 0 && y == 0) {
if (nd)cnt[i] = 2, ans |= (1ll << i);
else cnt[i] = 0;
nd = 0;
}
else if (x == 1 && y == 1) {
if (nd) { puts("-1"); return 0; }
else cnt[i] = 1;
nd = 0;
}
else if (x == 1 && y == 0) {
if (nd)cnt[i] = 2, ans |= (1ll << i);
else cnt[i] = 0;
nd = 1;
}
else {
if (nd)cnt[i] = 1;
else { puts("-1"); return 0; }
nd = 1;
}
}
if (nd == 1) { puts("-1"); return 0; }
for (int i = 50; i >= 0; i--) {
if (cnt[i] == 1 && ans + (1ll << i) <= a[1]) {
ans += (1ll << i);
}
}
if (ans > a[1] || ans == 0)puts("-1");
else printf("%lld\n", a[1] - ans);
return 0;
}
|
