A 多边形
题目大意 ： 求正 n 边形选出 m 个顶点组成的凸包恰有 k 个锐角的方案数
-
发现k>3的情况都无解，原因是，一个锐角三个点所在的弧一定得大于圆的一半。也因此锐角都是相邻的
-
然后枚举k是3，2，1，推式子，k是0的时候就那总方案数减去1，2，3的
-
枚举k，然后枚举一个点，再枚举第二个点，然后组合数求剩下的点方案数，化简之后就都成O(1)的。
-
对于每个k，m=3的情况都要特殊推
Code
Show Code
#include <cstdio>
using namespace std;
const int N = 1e6 + 5, M = 1000109107;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int n, m, k, n2, fac[N], inv[N];
int Pow(int a, int k, int ans = 1) {
for (; k; k >>= 1, a = 1ll * a * a % M)
if (k & 1) ans = 1ll * ans * a % M;
return ans;
}
void Init(int n) {
fac[0] = 1;
for (int i = 1; i <= n; ++i)
fac[i] = 1ll * fac[i-1] * i % M;
inv[n] = Pow(fac[n], M - 2);
for (int i = n; i >= 1; --i)
inv[i-1] = 1ll * inv[i] * i % M;
}
int C(int n, int m) {
if (n < m) return 0;
return 1ll * fac[n] * inv[m] % M * inv[n-m] % M;
}
int Cal(int k) {
if (k == 0) return (1ll * C(n, m) - Cal(1) - Cal(2) - Cal(3) + 3ll * M) % M;
if (k == 1) {
if (m == 3) return 0;
return (1ll * n2 * C(n2, m-2) - C(n2, m-1) - 2*C(n2+1, m-1) + 1ll * M) % M * n % M;
}
if (k == 2) {
if (m == 3) return 1ll * n * n2 * (n2-1) / 2 % M;//
return 1ll * (C(n2+1, m-1) + C(n2, m-1)) * n % M;
}
if (k == 3) {
if (m == 3) return 1ll * n * n2 * (n2+1) / 6 % M;
return 0;
}
}
int main() {
freopen("polygon.in", "r", stdin);
freopen("polygon.out", "w", stdout);
Init(N-1);
for (int T = read(); T; --T) {
n = read(); m = read(); k = read();
n2 = n / 2;
printf("%d
", Cal(k));
}
}
B 仙人掌
题目大意 ： 给一颗树，每次将相邻的节点权值都加1，问这些节点权值的异或和
-
如果把数从最低位开始放入trie树，想让所有数都加一，操作其实是把后面连续的一段1改为0，然后下一个0改成1，
-
所以可以从根开始，把左右儿子交换，然后再递归原来是1的儿子（现在是0）
-
想得到所有数的异或和，就维护个每个位上1的个数，修改的时候连这个一起也改一下
-
所以可以把自己的值放到父亲的那颗trie树里，然后操作的时候就只需要给自己的tire树里全部加一然后求异或和，然后再在父亲的父亲的trie树上把父亲的值改了
Code
Show Code
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5e5 + 5, M = 1000109107;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
struct Edge {
int n, t;
}e[N*2];
int h[N], edc;
void Add(int x, int y) {
e[++edc] = (Edge) {h[x], y}; h[x] = edc;
}
int n, m, fa[N], c[N], s[N], ch[N*40][2], a[N][20], sz[N*40], trc, ans;
void Insert(int x, int w, int op) {
for (int i = 0, p = x; i <= 18; ++i) {
bool k = w & 1 << i;
if (!ch[p][k]) ch[p][k] = ++trc;
p = ch[p][k]; sz[p] += op;
if (k) a[x][i] += op;
}
}
void Dfs(int x) {
if (fa[x]) Insert(fa[x], 0, 1);
for (int i = h[x], y; i; i = e[i].n)
if ((y = e[i].t) != fa[x]) fa[y] = x, Dfs(y);
}
int main() {
freopen("cactus.in", "r", stdin);
freopen("cactus.out", "w", stdout);
trc = n = read(); m = read();
for (int i = 1; i < n; ++i) {
int x = read(), y = read();
Add(x, y); Add(y, x);
}
Dfs(1);
for (int t = 1; t <= m; ++t) {
int x = read(), fx = fa[x], sum = 0; c[x]++;
if (fx) sum = ++s[fx];
if (fa[fx]) {
sum += c[fa[fx]];
Insert(fa[fx], sum-1, -1);
Insert(fa[fx], sum, 1);
}
for (int i = 0, p = x; i <= 18; ++i) {
a[x][i] += sz[ch[p][0]] - sz[ch[p][1]];
swap(ch[p][0], ch[p][1]); p = ch[p][0];
if (a[x][i] & 1) sum ^= 1 << i;
}
ans = (ans + (1ll * t * t + t) % M * sum) % M;
}
printf("%d
", ans);
return 0;
}
C 多项式 (Unaccepted)
题目大意 ：
Code
Show Code