[LA 5135][WF2011]Mining Your Own Business
点双开坑……
考虑每个点双。如果一个点双有一个（全局的）割点，那么必须要在该点双的一个非割点处建一个出口（否则割掉这个割点会出事）。如果一个点双的割点多于一个，那么其实并没有必要在这里建出口，因为不管割掉那个点，这个点双里面的点总有办法走到一个只有一个割点的点双里。
有一种特殊情况……就是整个图是点双联通的，这样的话随便找两个点建出口就行了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <map>
const int maxn = 100005;
std::vector<int> G[maxn];
int n;
void clear_graph() {
for(int i = 1; i <= 100000; i ++) {
G[i].clear();
}
}
void add_edge(int u, int v) {
G[u].push_back(v); G[v].push_back(u);
}
std::map<int, int> ma;
int sz;
int trace(int x) {
if(ma.count(x)) {
return ma[x];
} else {
ma[x] = ++ sz;
return sz;
}
}
using Edge = std::pair<int, int>;
int dcnt, bcc_cnt;
int pre[maxn];
bool is_cut[maxn]; int bccno[maxn];
std::vector<int> bcc[maxn];
std::stack<Edge> S;
int dfs(int x, int fa = -1) {
pre[x] = ++ dcnt; int low = pre[x];
int cld = 0;
for(auto v : G[x]) {
Edge e = std::make_pair(x, v);
if(!pre[v]) {
S.push(e); cld ++;
int lowv = dfs(v, x);
low = std::min(low, lowv);
if(lowv >= pre[x]) {
is_cut[x] = true;
bcc_cnt ++; bcc[bcc_cnt].clear();
while(true) {
Edge ee = S.top(); S.pop();
int f = ee.first, g = ee.second;
if(bccno[f] != bcc_cnt) {
bccno[f] = bcc_cnt; bcc[bcc_cnt].push_back(f);
}
if(bccno[g] != bcc_cnt) {
bccno[g] = bcc_cnt; bcc[bcc_cnt].push_back(g);
}
if(f == x && g == v) break;
}
}
} else if(pre[v] < pre[x] && v != fa) {
S.push(e); low = std::min(low, pre[v]);
}
}
if(fa < 0 && cld == 1) is_cut[x] = false;
return low;
}
void calc_bcc() {
std::fill(pre, pre + 1 + sz, 0);
std::fill(is_cut, is_cut + 1 + sz, false);
std::fill(bccno, bccno + 1 + sz, 0);
dcnt = bcc_cnt = 0;
for(int i = 1; i <= sz; i ++) {
if(!pre[i]) dfs(i);
}
}
using ll = long long;
int main() {
int cs = 0;
while(scanf("%d", &n) == 1) {
if(n == 0) break;
cs ++; sz = 0; ma.clear();
clear_graph();
for(int i = 1; i <= n; i ++) {
int u, v; scanf("%d%d", &u, &v);
u = trace(u); v = trace(v);
add_edge(u, v);
}
calc_bcc();
ll a1 = 0, a2 = 1LL;
for(int i = 1; i <= bcc_cnt; i ++) {
int cnum = 0;
for(auto x : bcc[i]) {
if(is_cut[x]) cnum ++;
}
if(cnum == 1) {
a1 ++;
a2 *= (ll(bcc[i].size() - 1));
}
}
if(bcc_cnt == 1) {
a1 = 2; ll s = bcc[1].size();
a2 = s * (s - 1LL) / 2LL;
}
printf("Case %d: %lld %lld\n", cs, a1, a2);
}
return 0;
}
[UOJ 195][ZJOI2016]大♂森林
ETT野蛮，LCT文明，，，
换生长结点这个操作非常的麻烦。所以考虑给每个生长操作建立一个虚点，每个实点（就是在树中真实存在的点）向他之前最晚建立的一个虚点认父。
然后虚点初始的时候应该向上一次的那个虚点认父（我们可以近似的认为第一个虚点就是1）。然后我们用类似于扫描线的做法，等到了虚点存在的区间里就把它爸爸改成相应的实点，出去了相应区间之后就再改回来。这样这题就很好做了，我们认为虚点点权为0，实点点权为1，然后查询就好做了。
然后还有一点细节问题……比如说换生长结点的时候如何处理x在某一棵树里不存在的情况。但这个不难处理，因为同一个编号的结点一定分布编号连续的一段树里，所以真实起作用的操作范围可以认定为数据给出的操作范围和x的分布区间的交。
再有一点就是查询的时候……如果直接查询两点间splay的和的话，可能会忽略掉一些本来在原图上该有的实点。所以我们要求两点到根的距离，再用LCA去掉不需要的。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
const int maxn = 100005;
const int maxm = 200005;
const int maxs = maxm + maxm;
struct Node {
Node *fa, *ch[2];
int val, sumv;
bool rev;
int d() {
return ((this == fa -> ch[1]) ? 1 : 0);
}
void sc(Node *c, int dir) {
ch[dir] = c;
c -> fa = this;
}
void maintain() {
sumv = ch[0] -> sumv + ch[1] -> sumv + val;
}
void paint() {
rev = !rev;
std::swap(ch[0], ch[1]);
}
void pushdown() {
if(rev) {
ch[0] -> paint();
ch[1] -> paint();
rev = false;
}
}
};
Node pool[maxs];
Node *nil, *cur;
void init_pool() {
nil = cur = pool;
nil -> val = nil -> sumv = 0;
nil -> rev = false;
nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
}
#define T(x) (pool + (x))
Node *refresh(Node *x, int val = 0) {
x -> val = x -> sumv = val;
x -> rev = false;
x -> fa = x -> ch[0] = x -> ch[1] = nil;
return x;
}
bool is_root(Node *x) {
return (x -> fa == nil || (x -> fa -> ch[0] != x && x -> fa -> ch[1] != x));
}
void zig(Node *x) {
Node *y = x -> fa; int d = x -> d();
if(is_root(y)) {
x -> fa = y -> fa;
} else {
y -> fa -> sc(x, y -> d());
}
y -> sc(x -> ch[1 ^ d], d);
x -> sc(y, 1 ^ d);
y -> maintain(); x -> maintain();
}
void splay(Node *x) {
while(!is_root(x)) {
Node *y = x -> fa;
if(!is_root(y)) y -> fa -> pushdown();
y -> pushdown(); x -> pushdown();
if(!is_root(y)) {
if((x -> d()) ^ (y -> d())) {
zig(x);
} else {
zig(y);
}
}
zig(x);
}
// x -> maintain();
}
Node *access(Node *x) {
Node *nx = x, *y = nil;
Node *ct = T(1);
while(x != nil) {
splay(x); x -> pushdown();
if(x -> fa == nil) ct = x;
x -> sc(y, 1); x -> maintain();
y = x; x = x -> fa;
}
splay(nx); return ct;
}
Node *evert(Node *x) {
access(x); x -> paint();
return x;
}
void link(Node *x, Node *y) {
evert(x); x -> fa = y;
}
void cut(Node *x) {
access(x);
x -> ch[0] -> fa = nil;
x -> ch[0] = nil; x -> maintain();
}
void cut(Node *x, Node *y) {
evert(x); access(y);
int d = x -> d();
y -> ch[d] = nil; y -> maintain();
x -> fa = nil;
}
int ans[maxm];
using pii = std::pair<int, int>;
int n;
pii seg_and(int a, int b, int x, int y) {
if(a > x) {
std::swap(a, x), std::swap(b, y);
}
if(b < x) return std::make_pair(n + 1, n + 1);
if(b >= y) return std::make_pair(x, y);
return std::make_pair(x, b);
}
int ope[maxm][4];
int seg[maxm][2];
Node *bef[maxm];
std::vector<int> beg[maxn], end[maxn];
std::vector<int> query[maxn];
// #define OUTP
// #define LOCAL
int main() {
#ifdef OUTP
freopen("forest1.in", "r", stdin);
freopen("out", "w+", stdout);
#endif
int m; scanf("%d%d", &n, &m);
init_pool(); refresh(T(1), 1);
int cnt0 = 1, cnt1 = 0, cnt2 = 0;
Node *last1 = T(1);
seg[1][0] = 1; seg[1][1] = n;
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d", &ope[i][0], &ope[i][1], &ope[i][2]);
if(ope[i][0]) {
scanf("%d", &ope[i][3]);
}
if(ope[i][0] == 0) {
int c = ++ cnt0;
refresh(T(c), 1);
link(last1, T(c));
seg[c][0] = ope[i][1]; seg[c][1] = ope[i][2];
#ifdef LOCAL
printf("Node %d : (%d, %d)\n", c, seg[c][0], seg[c][1]);
#endif
} else if(ope[i][0] == 1) {
Node *n1 = T(m + i);
refresh(n1); link(n1, bef[i] = last1);
int l = ope[i][1], r = ope[i][2], x = ope[i][3];
auto s = seg_and(l, r, seg[x][0], seg[x][1]);
l = s.first, r = s.second;
#ifdef LOCAL
printf("Change : (%d, %d) -> %d\n", l, r, x);
#endif
beg[l].push_back(i); end[r + 1].push_back(i);
last1 = n1;
} else {
int x = ope[i][1], u = ope[i][2], v = ope[i][3];
query[x].push_back(i);
}
}
for(int i = 1; i <= n; i ++) {
for(auto id : end[i]) {
Node *n1 = T(m + id);
cut(n1, T(ope[id][3])); link(n1, bef[id]);
}
for(auto id : beg[i]) {
Node *n1 = T(m + id);
cut(n1, bef[id]); link(n1, T(ope[id][3]));
}
for(auto id : query[i]) {
int u = ope[id][2], v = ope[id][3];
evert(T(1)); access(T(u));
int ret = T(u) -> sumv;
Node *lca = access(T(v));
ret += T(v) -> sumv;
access(lca);
ret -= lca -> sumv;
ret -= lca -> sumv - 1;
ans[id] = ret - 1;
}
}
for(int i = 1; i <= m; i ++) {
if(ope[i][0] == 2) {
printf("%d\n", ans[i]);
}
}
return 0;
}
[UOJ 113][UER #2]手机的生产
神哎……
既然与的优先级比或高，那么我们就可以用或把程序切成若干段，每一段的值决定了最后的取值。
考虑从左往右计算某一段。如果有一个手机某一段运算结果为0，那么它会继续往下运算，反之则会停止运算。
对于每一个在前\(i\)段的值都是0，然后开始跑第\(i + 1\)段的手机。他们都会额外产生\(l\)（这一段的fork个数）个手机，并且由于这些手机一被生产出来的返回值就是0，所以新的这些手机在这一段取值为0。而原来的老手机，在这一段的取值事1，于是之后的运算就不会接着做了。
这样一来，我们就可以动态维护在之前的段里的返回值全是0的手机，然后就可以做了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
const int maxn = 100005;
const ll ha = 998244353LL;
bool op[maxn];
int main() {
std::vector<int> vec;
int last = 0;
int n; scanf("%d", &n);
for(int i = 1; i <= (n - 1); i ++) {
char buf[5]; scanf("%s", buf);
if(buf[0] == '|') {
vec.push_back(i - last);
last = i;
}
}
vec.push_back(n - last);
ll pre0 = 1LL;
ll ans = 1LL;
for(auto x : vec) {
ans += (pre0 * (ll(x))) % ha; ans %= ha;
pre0 = (pre0 * (ll(x))) % ha;
}
printf("%lld\n", ans);
return 0;
}
[UOJ 48][UR #3]核聚变反应堆
先去考虑两个变量的sgcd怎么求……我们先求出他们的gcd，然后在除掉一个最小的质因子即可。
那么我们先把\(a_1\)分解质因数，然后所有数和它求一个gcd，然后去去掉一个尽可能小的质因子。注意到一个数\(p\)的质因子数量是\(O(\log p)\)级别的，所以每一个数找到要除的那个最小的质因子只需要\(O(\log a_1)\)的时间。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
const int maxn = 100005;
using ll = long long;
ll V[maxn]; int vcnt = 0;
void des(ll x) {
ll m = (ll)sqrt(x + 0.5);
for(ll i = 2; i <= m; i ++) {
if(x % i == 0) {
V[vcnt ++] = i;
while(x % i == 0) x /= i;
}
}
if(x > 1LL) V[vcnt ++] = x;
}
ll gcd(ll a, ll b) {
if(!b) return a;
else return gcd(b, a % b);
}
ll A[maxn];
int main() {
int n; scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%lld", &A[i]);
}
des(A[1]);
for(int i = 1; i <= n; i ++) {
if(i > 1) putchar(' ');
ll bs = gcd(A[i], A[1]);
if(bs == 1) {
printf("-1"); continue;
}
for(int j = 0; j < vcnt; j ++) {
if(A[i] % V[j] == 0) {
bs /= V[j];
break;
}
}
printf("%lld", bs);
}
puts("");
return 0;
}
[CF 618F]Double Knapsack
我zzs就算掉光rating，R2爆炸，也不会做你们半道构造题！
啊构造题真好玩（一转）。
不妨钦定\(A\)中所有元素的和不大于\(B\)的。然后把两个集合按照任意顺序搞成一个序列，然后求出两者的前缀和\(SA\)和\(SB\)。
考虑对于0...n的\(SA_i\)，找出\(SB\)中不大于他的数中最大的一个（不妨设为\(SB_j\)），可以发现有\(0\leq SA_i - SB_j\leq n - 1\)（不然\(j\)还能再大）。然后发现：我们处理的\(i\)和\(j\)的数对有\(n + 1\)组，但是\(SA_i - SB_j\)的取值却只有N种！也就是说一定存在\(i\neq i'\)且\(j\neq j'\)满足\(SA_i - SB_j = SA_{i'} - SB_{j'}\)。
我们找出两对这样的数对，移一下项就可以构造一组解了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
using ll = long long;
using pii = std::pair<int, int>;
int n;
void gen_S(int *arr, ll *S) {
S[0] = 0LL;
for(int i = 1; i <= n; i ++) {
S[i] = (S[i - 1] + (ll(arr[i])));
}
}
const int maxn = 1000005;
std::vector<pii> cs[maxn];
int main() {
scanf("%d", &n);
int *A = (int*)calloc(n + 1, sizeof(int));
int *B = (int*)calloc(n + 1, sizeof(int));
ll sum_A = 0LL, sum_B = 0LL;
for(int i = 1; i <= n; i ++) {
scanf("%d", &A[i]); sum_A += A[i];
}
for(int i = 1; i <= n; i ++) {
scanf("%d", &B[i]); sum_B += B[i];
}
bool flip = false;
if(sum_A > sum_B) {
flip = true;
std::swap(A, B);
std::swap(sum_A, sum_B);
}
ll *SA = (ll*)calloc(n + 1, sizeof(ll));;
ll *SB = (ll*)calloc(n + 1, sizeof(ll));;
gen_S(A, SA); gen_S(B, SB);
for(int i = 0; i <= n; i ++) {
int j = std::upper_bound(SB, SB + n + 1, SA[i]) - SB - 1;
ll val = SA[i] - SB[j];
cs[val].push_back(std::make_pair(i, j));
}
int l1, r1, l2, r2;
for(int i = 0; i < n; i ++) {
if(cs[i].size() > 1) {
int i1 = cs[i][0].first;
int j1 = cs[i][0].second;
int i2 = cs[i][1].first;
int j2 = cs[i][1].second;
if(i1 > i2) {
std::swap(i1, i2);
std::swap(j1, j2);
}
l1 = i1; r1 = i2;
l2 = j1; r2 = j2;
break;
}
}
if(flip) {
std::swap(l1, l2);
std::swap(r1, r2);
}
printf("%d\n", r1 - l1);
for(int i = l1 + 1; i <= r1; i ++) {
if(i > l1 + 1) putchar(' ');
printf("%d", i);
}
putchar('\n');
printf("%d\n", r2 - l2);
for(int i = l2 + 1; i <= r2; i ++) {
if(i > l2 + 1) putchar(' ');
printf("%d", i);
}
putchar('\n');
free(A); free(B);
free(SA); free(SB);
return 0;
}
[UOJ 21][UR #1]缩进优化
神题啊……
考虑让答案最小不好做，那么我们想，把连续的一段空格变成一个TAB（假设TAB长度为\(x\)）就是减少\(x - 1\)空格，那么我们尝试去最大化减小的空格的量。
然后考虑枚举\(x\)是啥，然后去算减少的空格的量。对于任意\(a_i\)，减少的空格量就是\((x-1)\lfloor\frac{a_i}{x}\rfloor\)，这似乎可以整除分块哎……
但是会被T掉。我们想，其实我们对任意\(x\)，我们去枚举\(\lfloor\frac{a_i}{x}\rfloor\)就行啦，要查询满足条件的\(a_i\)数量可以预处理一个权值前缀和然后就能\(O(1)\)做啦、
假设\(X = \max\{a_i\}\)，那么每一个\(x\)对时间复杂度的贡献就是\(O(\frac{X}{x})\)。这不就是调和级数吗？所以时间复杂度事\(O(X\ln X)\)。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
const int maxn = 1000005;
typedef long long ll;
int a[maxn], C[maxn];
int n, bd;
void process() {
for(int i = 1; i <= n; i ++) {
C[a[i]] ++;
}
for(int i = 1; i <= bd; i ++) {
C[i] += C[i - 1];
}
}
ll sum;
ll query(int x, int p) {
int l = x * p;
int r = x * (p + 1) - 1;
if(r > bd) r = bd;
return (C[r] - C[l - 1]);
}
ll calc(int x) {
ll delta = 0;
for(int i = 1; i <= (bd / x); i ++) {
ll cnt = query(x, i);
delta += (ll(i)) * cnt * (ll(x - 1));
}
#ifdef LOCAL
printf("ans of %d : %lld\n", x, sum - delta);
#endif
return (sum - delta);
}
int main() {
scanf("%d", &n);
sum = 0LL; bd = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
bd = std::max(bd, a[i]);
sum += a[i];
}
process();
ll ans = sum;
for(int i = 1; i <= bd; i ++) {
ans = std::min(ans, calc(i));
}
printf("%lld\n", ans);
return 0;
}
[UOJ 62][UR #5]怎样跑得更快
一年前看的反演神题……（然后现在才A）
[CodeChef BWGAME]Black-white Board Game
ao劲啊这题，，，
看到那个逆序对奇偶性就想到了行列式（考虑行列式的定义）……其实最后要判定的就是该矩阵行列式的正负性（或者是0）。
这个东西肯定可以高消搞成上三角，然后行列式就很好求了。但高消事\(O(n^3)\)的，会T掉。
考虑怎么去优化这个高消。首先在消元顺序合理的情况下，一定可以让矩阵在整个过程中一直是01矩阵。具体的实现方式，就是考虑从小到大对每个变量进行消元的时候，包含该变量的方程很多，并且他们两两之间一定是满足一个的全1段事另一个的前缀。那么用最短的那一段进行消元即可。
考虑到其他方程被消之后最靠左的1的位置会全部变成另一个位置，所以可以考虑使用可并堆维护各个方程。同时，为了求每个方程当前最靠左的1的位置，我搞了个并查集（逃
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <ext/pb_ds/priority_queue.hpp>
using R = double;
// using GG = __gnu_pbds::priority_queue<int>;
const int maxn = 100005;
const R eps = 1e-8;
inline int sign(R x) {
if(fabs(x) < eps) {
return 0;
} else {
if(x < 0.00) {
return -1;
} else {
return 1;
}
}
}
int seg[maxn][2];
namespace BF {
R A[105][105];
inline int det(int n) {
int flag = 1;
for(int i = 1; i <= n; i ++) {
int r = i;
for(int j = i + 1; j <= n; j ++) {
if(fabs(A[j][i]) > fabs(A[i][i])) {
r = j;
}
}
if(r != i) {
flag *= -1;
for(int j = i; j <= n; j ++) {
std::swap(A[i][j], A[r][j]);
}
} else {
if(sign(A[i][i]) == 0) {
return 0;
}
}
for(int j = i + 1; j <= n; j ++) {
if(sign(A[j][i]) == 0) continue;
double f = A[j][i] / A[i][i];
for(int k = i; k <= n; k ++) {
A[j][k] -= A[i][k] * f;
}
}
}
int ret = flag;
for(int i = 1; i <= n; i ++) {
ret *= sign(A[i][i]);
}
return ret;
}
inline void solve(int n) {
for(int i = 1; i <= n; i ++) {
int L = seg[i][0], R = seg[i][1];
for(int j = 1; j <= n; j ++) {
if(L <= j && j <= R) {
A[i][j] = 1;
} else {
A[i][j] = 0;
}
}
}
int v = (det(n));
if(v == -1) {
puts("Fedor");
} else if(v == 0) {
puts("Draw");
} else {
puts("Alex");
}
}
};
namespace CT {
/*
struct Node {
int l, r, id;
bool operator <(const Node &res) const {
if(l == res.l) {
if(r == res.r) {
return id < res.id;
} else {
return r < res.r;
}
} else {
return l < res.l;
}
}
bool operator >(const Node &res) const {
if(l == res.l) {
if(r == res.r) {
return id > res.id;
} else {
return r > res.r;
}
} else {
return l > res.l;
}
}
bool operator ==(const Node &res) const {
return (l == res.l) && (r == res.r) && (id == res.id);
}
};
*/
struct N2 {
int r, id;
N2() {
r = 0; id = 0;
}
N2(int x, int y) {
r = x; id = y;
}
bool operator <(const N2 &res) const {
if(r == res.r) {
return id < res.id;
} else {
return r < res.r;
}
}
bool operator >(const N2 &res) const {
if(r == res.r) {
return id > res.id;
} else {
return r > res.r;
}
}
bool operator ==(const N2 &res) const {
return (r == res.r) && (id == res.id);
}
};
/* struct Node {
Node *fa, *ch[2];
N2 v; int l;
int setv;
int d() {
return ((this == fa -> ch[1]) ? 1 : 0);
}
void sc(Node *c, int dir) {
ch[dir] = c;
c -> fa = this;
}
int cmp(const N2 &v2) const {
if(v == v2) {
return -1;
} else {
if(v2 < v) {
return 0;
} else {
return 1;
}
}
}
void paint(int x) {
if(l == -1) return;
l = x; setv = x;
}
void pushdown(int x) {
if(setv != -1) {
ch[0] -> paint(setv);
ch[1] -> paint(setv);
setv = -1;
}
}
};
Node pool[maxn]; std::queue<int> FQ;
Node *nil, *cur;
void init_pool() {
nil = cur = pool;
nil -> l = nil -> setv = -1;
nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
}
Node *alloc_node(N2 x, int L) {
Node *ret;
if(FQ.empty()) {
ret = ++ cur;
} else {
ret = FQ.front(); FQ.pop();
}
ret -> v = x;
ret -> l = L; ret -> setv = -1;
ret -> fa = ret -> ch[0] = ret -> ch[1] = nil;
return ret;
}
inline bool is_root(Node *o) {
return (o -> fa == nil)
}
inline void zig(Node *x) {
int d = x -> d(); Node *y = x -> fa;
if(is_root(y)) {
x -> fa = y -> fa;
} else {
y -> fa -> sc(x, y -> d());
}
y -> sc(x -> ch[d ^ 1], d);
x -> sc(y, d ^ 1);
}
void pdw_path(Node *x) {
if(!is_root(x)) pdw_path(x -> fa);
x -> pushdown();
}
inline void splay(Node *x) {
pdw_path(x);
while(!is_root(x)) {
Node *y = x -> fa;
if(!is_root(y)) {
if((x -> d()) ^ (y -> d())) {
zig(x);
} else {
zig(y);
}
}
zig(x);
}
}
Node *insert(Node *o, Node *x) {
if(o == nil) return x;
Node *last = o;
int d;
while(o != nil) {
o -> pushdown(); last = o;
d = o -> cmp(x -> v);
o = o -> ch[d];
}
x -> ch[0] = x -> ch[1] = nil;
last -> sc(x, d);
splay(x); return x;
}
Node *top(Node *x) {
Node *ret = x;
while(x -> ch[0] == 0) {
x -> paint
}
} */
int par[maxn * 2];
int get_fa(int x) {
if(par[x] == x) return x;
else return (par[x] = get_fa(par[x]));
}
void merge(int dir, int src) {
dir = get_fa(dir); src = get_fa(src);
if(dir == src) return;
par[src] = dir;
}
bool is_same(int x, int y) {
return (get_fa(x) == get_fa(y));
}
using heap = __gnu_pbds::priority_queue<N2, std::greater<N2> >;
heap Q[maxn];
int id[maxn], mp[maxn];
int det(int n) {
int flag = 1;
for(int i = 1; i <= n; i ++) {
Q[i].clear();
}
for(int i = 1; i <= 2 * n; i ++) {
par[i] = i;
}
for(int i = 1; i <= n; i ++) {
id[i] = mp[i] = i;
int L = seg[i][0], R = seg[i][1];
Q[L].push(N2(R, i));
merge(L, n + i);
}
for(int i = 1; i <= n; i ++) {
if(Q[i].empty()) {
return 0;
}
int p = id[i];
if(!(get_fa(p + n) <= i && seg[p][1] == (Q[i].top()).r)) {
flag *= -1;
int np = (Q[i].top()).id;
#ifdef LOCAL
printf("Swaping %d and %d.\n", p, np);
#endif
int nv = mp[np];
std::swap(id[i], id[nv]);
std::swap(mp[np], mp[p]);
}
p = id[i];
Q[i].pop();
int r = seg[p][1];
if(Q[i].size() > 0 && (Q[i].top()).r == r) {
return 0;
}
if(r < n) {
Q[r + 1].join(Q[i]);
merge(r + 1, i);
}
}
return flag;
}
void solve(int n) {
int v = det(n);
if(v == -1) {
puts("Fedor");
} else if(v == 0) {
puts("Draw");
} else {
puts("Alex");
}
}
};
int main() {
int T; scanf("%d", &T);
while(T --) {
int n; scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%d%d", &seg[i][0], &seg[i][1]);
}
if(n <= 100) {
BF::solve(n);
} else {
CT::solve(n);
}
}
return 0;
}
[BZOJ 3456]城市规划
aji多项式求逆毁我青春，，，
设\(f_i\)表示\(i\)个点的有标号无向联通图，考虑所有可能的图（记\(F_i\)为\(i\)个点的有标号无向图，显然\(F_i = 2^{\binom{i}{2}}\)）和\(f\)的关系（使用图计数的经典套路：枚举1所在的联通块大小）：
\[F_n = \sum_{i = 1}^n \binom{n-1}{i-1} f_i F_{n - i}\]
看起来事卷积？但是这个卷积没有办法直接用FFT/NTT求（当然分离一下项啊，移下项就可以分治NTT力）。
考虑进一步化简柿子。完全展开后会发现右边有个非常碍眼的\((n-1)!\)，所以两边除一下：
\[\frac{F_n}{(n-1)!} =\sum_{i = 1}^n \frac{f_i}{(i-1)!}\cdot \frac{F_{n - i}}{(n - i)!}\]
然后这个问题就很毒瘤了：我们要求的答案多项式（除上那个阶乘）和一个已知多项式做卷积，可以得到另一个已知多项式……这样就需要多项式除法了，于是乎多项式逆元派上了用场。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 1020010;
const ll ha = 1004535809LL;
const ll bs = 3LL;
ll pow_mod(ll a, ll b) {
ll ans = 1LL, res = a % ha;
while(b) {
if(1LL & b) ans = (ans * res) % ha;
res = (res * res) % ha;
b >>= 1;
}
return ans;
}
ll inv(ll x) {
return pow_mod(x, ha - 2LL);
}
int flip(int bi, int x) {
int ans = 0;
for(int i = 0; i < bi; i ++) {
if((1 << i) & x) {
ans += (1 << (bi - i - 1));
}
}
return ans;
}
void NTT(ll *A, int bi, bool flag = false) {
int n = 1 << bi;
for(int i = 0; i < n; i ++) {
int v = flip(bi, i);
if(v < i) std::swap(A[v], A[i]);
}
for(int L = 1; L < n; L <<= 1) {
ll xi = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)));
if(flag) xi = inv(xi);
for(int i = 0; i < n; i += (L << 1)) {
ll w = 1LL;
for(int j = i; j < i + L; j ++) {
ll v1 = A[j], v2 = A[j + L];
A[j] = (v1 + (w * v2) % ha) % ha;
A[j + L] = (v1 - (w * v2) % ha + ha) % ha;
w = (w * xi) % ha;
}
}
}
}
void poly_mul(ll *A, ll *B, int bi, ll *C) {
static ll T1[maxn], T2[maxn];
int n = (1 << bi);
std::copy(A, A + n, T1);
std::copy(B, B + n, T2);
NTT(T1, bi); NTT(T2, bi);
#ifdef LOCAL
puts("poly_mul :");
for(int i = 0; i < (n); i ++) {
printf("%lld ", A[i]);
}
puts("");
for(int i = 0; i < (n); i ++) {
printf("%lld ", B[i]);
}
puts("");
for(int i = 0; i < (n); i ++) {
printf("%lld ", T1[i]);
}
puts("");
for(int i = 0; i < (n); i ++) {
printf("%lld ", T2[i]);
}
puts("");
#endif
for(int i = 0; i < n; i ++) {
T1[i] = (T1[i] * T2[i]) % ha;
}
#ifdef LOCAL
for(int i = 0; i < (n); i ++) {
printf("%lld ", T1[i]);
}
puts("");
#endif
NTT(T1, bi, true);
ll inv_n = inv(n);
for(int i = 0; i < n; i ++) {
T1[i] = (T1[i] * inv_n) % ha;
}
std::copy(T1, T1 + n, C);
#ifdef LOCAL
for(int i = 0; i < (n); i ++) {
printf("%lld ", C[i]);
}
puts("");
#endif
}
void poly_inv(int mod, ll *B, ll *BB) {
if(mod == 1) {
BB[0] = inv(B[0]);
} else {
poly_inv((mod + 1) >> 1, B, BB);
int bi = 0, sz = 1;
while(sz <= ((mod * 2) + 1)) {
bi ++; sz <<= 1;
}
ll inv_sz = inv(sz);
static ll tmp[maxn];
std::copy(B, B + mod, tmp);
std::fill(tmp + mod, tmp + sz, 0LL);
NTT(tmp, bi); NTT(BB, bi);
for(int i = 0; i < sz; i ++) {
tmp[i] = (tmp[i] * BB[i]) % ha;
tmp[i] = (tmp[i] * (ha - 1LL)) % ha;
tmp[i] = (tmp[i] + 2LL) % ha;
tmp[i] = (tmp[i] * BB[i]) % ha;
}
NTT(tmp, bi, true);
for(int i = 0; i < sz; i ++) {
tmp[i] = (tmp[i] * inv_sz) % ha;
}
std::copy(tmp, tmp + mod, BB);
std::fill(BB + mod, BB + sz, 0LL);
}
}
int main() {
static ll fac[maxn], A[maxn], B[maxn], BB[maxn];
int n; scanf("%d", &n);
int bi = 0, sz = 1;
while(sz <= n + 1) {
bi ++; sz <<= 1;
}
fac[0] = 1LL;
for(int i = 1; i <= n; i ++) {
fac[i] = (fac[i - 1] * (ll(i))) % ha;
}
B[0] = 1LL;
for(int i = 1; i <= n; i ++) {
B[i] = pow_mod(2LL, (ll(i)) * (ll(i - 1)) / 2LL);
B[i] = (B[i] * inv(fac[i])) % ha;
}
for(int i = 1; i <= n; i ++) {
A[i] = pow_mod(2LL, (ll(i)) * (ll(i - 1)) / 2LL);
A[i] = (A[i] * inv(fac[i - 1])) % ha;
}
poly_inv(n + 1, B, BB);
poly_mul(A, BB, bi, A);
printf("%lld\n", (A[n] * fac[n - 1]) % ha);
return 0;
}
[BZOJ 3328]PYXFIB
又学了个新套路呢qwq
题面要求的其实是：
\[\sum_{i = 0}^n [k|i]\binom{n}{i} F_i\]
不考虑那个\([k|i]\)，式子是非常像一个二项式展开的……
考虑构造矩阵的二项式展开，可以发现（其中\(A\)是斐波那契数列的二项式展开）：
\[(I + A)^n = \sum_{i = 0}^n \binom{n}{i} A^i\]
然后\(k=1\)的情况我们就会做辣！接下来的问题是，如何取出一个生成函数中次数为\(k\)倍数的项求和？
然后我们发现单位根有个非常优良的性质：
\[\frac{1}{k} \sum_{i=1}^{k} \xi_k^{ni} = [k|n]\]
这里的\(n\)是一个常数，但是其实可以对应到原式里的某一项的次数。至于证明……满足\(k|n\)的情况左边显然是一堆1取平均值，其他情况可以通过等比数列求和证明左边为0。
于是可以构造多项式\((I+xA)^n\)，把所有\(k\)次单位根做为\(x\)（求这个的话，可以利用原根）带入，对结果取平均值即可。
代码：
/**************************************************************
Problem: 3328
User: danihao123
Language: C++
Result: Accepted
Time:9080 ms
Memory:832 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
typedef long long ll;
typedef ll Mat[2][2];
ll p; int k;
ll pow_mod(ll a, ll b) {
ll ans = 1LL, res = a % p;
while(b) {
if(1LL & b) ans = (ans * res) % p;
res = (res * res) % p;
b /= 2LL;
}
return ans;
}
ll inv(ll x) {
return pow_mod(x, p - 2LL);
}
void factor(int x, std::vector<int> &V) {
int bd = sqrt(x + 0.5);
for(int i = 2; i <= bd; i ++) {
if(x % i == 0) {
V.push_back(i);
while(x % i == 0) x /= i;
}
}
if(x > 1) V.push_back(x);
}
int get_phi() {
if(p == 2LL) return 1LL;
std::vector<int> V;
factor(p - 1LL, V);
for(int i = 2; i <= (p - 1); i ++) {
bool flag = true;
for(int j = 0; j < V.size(); j ++) {
int up = (p - 1) / V[j];
if(pow_mod(i, up) == 1LL) {
flag = false; break;
}
}
#ifdef LOCAL
if(flag) printf("xi : %d\n", i);
#endif
if(flag) return i;
}
}
void mat_mul(const Mat &A, const Mat &B, int n, int m, int t, Mat &C) {
Mat D; memset(D, 0, sizeof(D));
for(int i = 0; i < n; i ++) {
for(int j = 0; j < t; j ++) {
for(int k = 0; k < m; k ++) {
D[i][j] = (D[i][j] + (A[i][k] * B[k][j]) % p) % p;
}
}
}
memcpy(C, D, sizeof(D));
}
void mat_pow(const Mat &A, int n, ll b, Mat &ret) {
Mat C, res;
memset(C, 0, sizeof(C));
for(int i = 0; i < n; i ++) C[i][i] = 1LL;
memset(res, 0, sizeof(res));
memcpy(res, A, sizeof(res));
while(b) {
if(1LL & b) mat_mul(C, res, n, n, n, C);
mat_mul(res, res, n, n, n, res);
b /= 2LL;
}
memcpy(ret, C, sizeof(C));
}
int main() {
int T; scanf("%d", &T);
while(T --) {
ll n;
scanf("%lld%d%lld", &n, &k, &p);
ll xi = pow_mod(get_phi(), (p - 1) / k);
ll w = 1LL;
ll ans = 0;
for(int i = 0; i < k; i ++) {
Mat X;
memset(X, 0, sizeof(X));
X[0][0] = X[1][0] = X[0][1] = w;
X[0][0] = (X[0][0] + 1LL) % p;
X[1][1] = (X[1][1] + 1LL) % p;
mat_pow(X, 2, n, X);
#ifdef LOCAL
puts("X : ");
for(int i = 0; i < 2; i ++) {
for(int j = 0; j < 2; j ++) {
printf("%lld ", X[i][j]);
}
puts("");
}
#endif
ans = (ans + X[0][0]) % p;
w = (w * xi) % p;
}
ans = (ans * inv(k)) % p;
printf("%lld\n", ans);
}
return 0;
}
