T1 计数
首先考虑计数有标号可重叠的方案数,容易发现此时 \(x,y\) 两维独立,因此考虑其中 \(1\) 维,设 \(f_{i,j}\) 表示此时考虑到第 \(i\) 对左右边界 \((x_{i,1},x_{i,2})\) ,离散化后的 \(x\) 坐标形成了 \(j\) 个点时的方案数,容易发现此时数轴上存在 \(j\) 个点,以及 \(j+1\) 个空白段,转移考虑 \(x_{i+1,1}\) 和 \(x_{i+1,2}\) 的位置,容易发现存在以下三种转移:
- \(x_{i+1,1}\) 和 \(x_{i+1,2}\) 均位于空白段内:
- \(x_{i+1,1}\) 和 \(x_{i+1,2}\) 一个位于原先点上,一个位于空白段内:
- \(x_{i+1,1}\) 和 \(x_{i+1,2}\) 均位于原有点上:
\(i\) 个矩形的方案数显然为 \((\sum_j f_{i,j})^2\) 。
考虑计算题目要求的答案,即 \(n\) 个矩形无标号,不可重叠的方案数,设答案为 \(ans(n)\) ,设有标号,可重叠方案数为 \(g(n)\) ,设一个长度为 \(n\) 的序列,总共有 \(i\) 种元素,要求每个元素至少出现一次的合法序列的数量为 \(h(n,i)\) ,容易发现这样的等量关系:
\[g(n)=\sum_{i=1}^{n}ans(i)h(n,i) \]直接 \(O(n^2)\) 递推即可。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int max1 = 5000;
const int mod = 1e9 + 7;
int n;
int g[2][max1 * 2 + 5], h[2][max1 + 5], now;
int f[max1 + 5];
int Binom ( int x )
{
return ( 1LL * x * ( x - 1 ) >> 1 ) % mod;
}
int Calc ( int x )
{
return ( 1LL * ( x + 1 ) * x >> 1 ) % mod;
}
void Add ( int &x, int y )
{
x += y;
if ( x >= mod )
x -= mod;
return;
}
int Quick_Power ( int base, int p )
{
int res = 1;
while ( p )
{
if ( p & 1 )
res = 1LL * res * base % mod;
p >>= 1;
base = 1LL * base * base % mod;
}
return res;
}
int main ()
{
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
scanf("%d", &n);
now = 0; g[now][0] = 1; h[now][0] = 1;
for ( int i = 1; i <= n; i ++ )
{
now ^= 1;
memset(g[now], 0, sizeof(int) * ( i + i + 1 ));
memset(h[now], 0, sizeof(int) * ( i + 1 ));
for ( int j = 0; j <= i + i - 2; j ++ )
{
g[now][j + 2] = ( g[now][j + 2] + 1LL * g[now ^ 1][j] * ( Binom(j + 1) + j + 1 ) ) % mod;
g[now][j + 1] = ( g[now][j + 1] + 2LL * g[now ^ 1][j] * Calc(j) ) % mod;
g[now][j] = ( g[now][j] + 1LL * g[now ^ 1][j] * Binom(j) ) % mod;
}
for ( int j = 0; j <= i - 1; j ++ )
{
h[now][j + 1] = ( h[now][j + 1] + 1LL * h[now ^ 1][j] * ( j + 1 ) ) % mod;
h[now][j] = ( h[now][j] + 1LL * h[now ^ 1][j] * j ) % mod;
}
int sum = 0;
for ( int j = 0; j <= i + i; j ++ )
Add(sum, g[now][j]);
sum = 1LL * sum * sum % mod;
for ( int j = 1; j <= i - 1; j ++ )
Add(sum, mod - 1LL * f[j] * h[now][j] % mod);
f[i] = 1LL * sum * Quick_Power(h[now][i], mod - 2) % mod;
}
printf("%d\n", f[n]);
return 0;
}
T2 AKEE的大砍刀
将原问题抽象,将含有公共边的三角形连边,容易发现形成树形结构,那么在原多边形上切一刀相当于断裂树上一条边,因此考虑维护每个小朋友吃的蛋糕所构成的虚树,对于每条边维护边权表示有多少虚树覆盖了这条边,此时我们的操作为树上一条链边权全局加,查询最小值以及最小值个数,很容易使用树剖 + 线段树维护,当然,由于笔者是废物,脑子经常断路,所以写了树剖套分块,具体而言对于每条重链分块即可,复杂度为 \(O(n\sqrt n)\) 。
code
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int max1 = 1e5;
const int inf = 0x3f3f3f3f;
int n, q, color[max1 + 5];
map < pair <int, int>, int > Map;
vector <int> edge[max1 + 5];
int siz[max1 + 5], deep[max1 + 5], father[max1 + 5], son[max1 + 5];
int top[max1 + 5], dfn[max1 + 5], rk[max1 + 5], dfs_clock;
set <int> point[max1 + 5];
int ans;
struct Part
{
int total, len, block;
vector <int> st, ed, bel;
vector <int> val, tag, Min, cnt;
void Build ()
{
len = sqrt(total), block = total / len;
st.resize(total + 1), ed.resize(total + 1), bel.resize(total + 1);
st[0] = ed[0] = 0;
for ( int i = 1; i <= block; i ++ )
{
st[i] = ed[i - 1] + 1;
ed[i] = i * len;
}
ed[block] = total;
for ( int i = 1; i <= block; i ++ )
for ( int j = st[i]; j <= ed[i]; j ++ )
bel[j] = i;
val.resize(total + 1);
tag.resize(total + 1);
Min.resize(total + 1);
cnt.resize(total + 1);
for ( int i = 1; i <= total; i ++ )
val[i] = 0;
for ( int i = 1; i <= block; i ++ )
{
tag[i] = Min[i] = 0;
cnt[i] = ed[i] - st[i] + 1;
ans += cnt[i];
}
return;
}
void Update ( int L, int R, int k )
{
if ( bel[L] == bel[R] )
{
int B = bel[L], BL = st[B], BR = ed[B];
if ( !( tag[B] + Min[B] ) )
ans -= cnt[B];
for ( int i = BL; i <= BR; i ++ )
val[i] += tag[B];
for ( int i = L; i <= R; i ++ )
val[i] += k;
tag[B] = 0;
Min[B] = inf;
for ( int i = BL; i <= BR; i ++ )
Min[B] = min(Min[B], val[i]);
cnt[B] = 0;
for ( int i = BL; i <= BR; i ++ )
cnt[B] += val[i] == Min[B];
if ( !Min[B] )
ans += cnt[B];
}
else
{
Update(L, ed[bel[L]], k);
Update(st[bel[R]], R, k);
for ( int i = bel[L] + 1; i <= bel[R] - 1; i ++ )
{
if ( !( tag[i] + Min[i] ) )
ans -= cnt[i];
tag[i] += k;
if ( !( tag[i] + Min[i] ) )
ans += cnt[i];
}
}
return;
}
}part[max1 + 5];
void Find_Heavy_Edge ( int now, int fa, int depth )
{
siz[now] = 1, deep[now] = depth, father[now] = fa, son[now] = 0;
int max_siz = 0;
for ( auto v : edge[now] )
{
if ( v == fa )
continue;
Find_Heavy_Edge(v, now, depth + 1);
siz[now] += siz[v];
if ( siz[v] > max_siz )
max_siz = siz[v], son[now] = v;
}
return;
}
void Connect_Heavy_Edge ( int now, int ancestor )
{
top[now] = ancestor;
dfn[now] = ++dfs_clock;
rk[dfs_clock] = now;
++part[top[now]].total;
if ( son[now] )
Connect_Heavy_Edge(son[now], ancestor);
for ( auto v : edge[now] )
{
if ( v == father[now] || v == son[now] )
continue;
Connect_Heavy_Edge(v, v);
}
return;
}
int Get_Lca ( int u, int v )
{
while ( top[u] != top[v] )
{
if ( deep[top[u]] < deep[top[v]] )
swap(u, v);
u = father[top[u]];
}
if ( deep[u] > deep[v] )
swap(u, v);
return u;
}
void Update ( int u, int v, int k )
{
while ( top[u] != top[v] )
{
if ( deep[top[u]] < deep[top[v]] )
swap(u, v);
part[top[u]].Update(1, deep[u] - deep[top[u]] + 1, k);
u = father[top[u]];
}
if ( deep[u] > deep[v] )
swap(u, v);
if ( u != v )
part[top[u]].Update(deep[u] - deep[top[u]] + 2, deep[v] - deep[top[u]] + 1, k);
return;
}
void Insert ( int x )
{
int c = color[x];
if ( !point[c].empty() )
{
int p = rk[*point[c].begin()], q = rk[*--point[c].end()], lca = Get_Lca(p, q);
if ( dfn[x] >= dfn[lca] && dfn[x] <= dfn[lca] + siz[lca] - 1 )
{
p = rk[*--point[c].upper_bound(dfn[x])];
lca = Get_Lca(p, x);
if ( *--point[c].end() > dfn[x] )
{
p = rk[*point[c].upper_bound(dfn[x])];
q = Get_Lca(p, x);
if ( deep[q] > deep[lca] )
lca = q;
}
}
Update(x, lca, 1);
}
point[c].insert(dfn[x]);
return;
}
void Delete ( int x )
{
int c = color[x];
point[c].erase(point[c].find(dfn[x]));
if ( !point[c].empty() )
{
int p = rk[*point[c].begin()], q = rk[*--point[c].end()], lca = Get_Lca(p, q);
if ( dfn[x] >= dfn[lca] && dfn[x] <= dfn[lca] + siz[lca] - 1 )
{
p = rk[*--point[c].upper_bound(dfn[x])];
lca = Get_Lca(p, x);
if ( *--point[c].end() > dfn[x] )
{
p = rk[*point[c].upper_bound(dfn[x])];
q = Get_Lca(p, x);
if ( deep[q] > deep[lca] )
lca = q;
}
}
Update(x, lca, -1);
}
return;
}
int main ()
{
freopen("akee.in", "r", stdin);
freopen("akee.out", "w", stdout);
int tmp[3];
scanf("%d", &n); n -= 2;
for ( int i = 1; i <= n; i ++ )
{
scanf("%d%d%d%d", &tmp[0], &tmp[1], &tmp[2], &color[i]);
sort(tmp, tmp + 3);
for ( int j = 0; j < 3; j ++ )
{
for ( int k = j + 1; k < 3; k ++ )
{
if ( Map.find(make_pair(tmp[j], tmp[k])) != Map.end() )
{
int v = Map[make_pair(tmp[j], tmp[k])];
edge[i].push_back(v); edge[v].push_back(i);
}
else
Map[make_pair(tmp[j], tmp[k])] = i;
}
}
}
for ( int i = 1; i <= n; i ++ )
part[i].total = 0;
Find_Heavy_Edge(1, 0, 0);
Connect_Heavy_Edge(1, 1);
for ( int i = 1; i <= n; i ++ )
if ( i == top[i] )
part[i].Build();
for ( int i = 1; i <= n; i ++ )
Insert(i);
printf("%d\n", ans - 1);
scanf("%d", &q);
int x, p;
while ( q -- )
{
scanf("%d%d", &x, &p);
Delete(x);
color[x] = p;
Insert(x);
printf("%d\n", ans - 1);
}
return 0;
}
T3 普及题
设第 \(i\) 个特殊点的临域集合为 \(S_i\) ,设 \(S=\cup S_i\) ,那么我们需要求解 \(|S|\) ,考虑构造一个长度为 \(\sum |S_i|\) 的序列 \(x\) ,对于每个集合 \(S_i\) ,设 \(a\) 为 \(S_i\) 中一个元素,设 \(a\) 在所有集合中的出现次数为 \(r\) ,那么 \(\tfrac{1}{r}\) 位于序列 \(x\) 中,容易发现 \(\sum x_i\) 就是我们需要求解的答案。
由于 \(x\) 序列的长度很容易计算,因此考虑求解 \(E(x_i)\) ,一种经典做法是随机取出 \(x\) 序列中一个数,然后求解所有数的平均值。
首先考虑随机的过程,选定当前数属于的集合(假设当前随机次数确定,可以直接计算当前集合内期望取出的数的个数),然后等概率随机集合内一个与当前集合对应点存在连边的点,由于可以确定当前集合的大小,可以随机排名后,通过字典序按位依次确定,设随机次数为 \(N\) ,此时复杂度为 \(O(Nk)\) 。
考虑求解当前随机点所对应的 \(r\) ,直接暴力的复杂度为 \(O(Tk)\) ,总复杂度为 \(O(NTk^2)\) ,然而题解表示 \(N\) 的大小需要为 \(O(k^2\epsilon^2)\) ,即使时限为 \(20s\) 也无法通过,考虑优化这个过程,预处理数组 \(f_{i,j,w}\) 表示在 \(i\) 这一维(一个点总共有 \(k\) 维),原图上 \(j\) 点与第 \(w\) 个特殊点的第 \(i\) 维是否存在连边,由于数组值只存在 \(0/1\) 状态,因此可以压位处理,考虑当前随机点与哪些特殊点存在连边,容易直接得到当前随机点的每一维与特殊点在这一维上的连边情况,但是由于这个矩阵是竖着压位存储的,而我们计算的信息(当前随机点与特殊点每一维上边的个数)需要这个矩阵横着压位存储才能使用 __builtin_popcount 快速计算,因此考虑对原矩阵进行转置。
考虑一种转置的方法,假设当前矩阵的行列相等并且均为 \(2\) 的整数幂,可以考虑分治,将原矩阵行列分成均等的四份,对四个小矩阵分别转置,之后交换左下角与右上角的矩阵,容易发现此时的矩阵就是转置矩阵,复杂度为 \(O(n^2\log n)\) ,由于矩阵每一位只存在 \(0/1\) 状态,因此这个过程可以使用神奇的二进制技巧实现,复杂度可以做到 \(O(\tfrac{n^2\log n}{w})\) ,可以通过本题。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <random>
#include <bitset>
#include <iostream>
using namespace std;
const int max1 = 32, max2 = 1000;
const int seed = 1204;
mt19937 rnd((unsigned long long)&seed);
double Sdouble ( double L, double R )
{
return uniform_real_distribution <double> (L, R) (rnd);
}
int n, m, k, s, T;
vector <int> edge[max2 + 5], rev_edge[max2 + 5];
bitset <max2 + 5> connect[max2 + 5];
int point[max1 + 5][max1 + 5];
unsigned int is_edge[max1 + 5][max2 + 5];
unsigned int tmp[max1 + 5], matrix[max1 + 5];
double f[max1 + 5][max1 + 5], sum[max1 + 5], total, ans;
int sp[max1 + 5], cnt;
int main ()
{
freopen("tech.in", "r", stdin);
freopen("tech.out", "w", stdout);
scanf("%d%d%d%d%d", &n, &m, &k, &s, &T);
for ( int i = 1, u, v; i <= m; i ++ )
{
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
connect[u][v] = connect[v][u] = 1;
}
for ( int i = 1; i <= T; i ++ )
for ( int j = 1; j <= k; j ++ )
scanf("%d", &point[i][j]);
for ( int i = 1; i <= n; i ++ )
{
sort(edge[i].begin(), edge[i].end());
edge[i].erase(unique(edge[i].begin(), edge[i].end()), edge[i].end());
int pre = 0;
for ( auto v : edge[i] )
{
for ( int j = pre + 1; j <= v - 1; j ++ )
rev_edge[i].push_back(j);
pre = v;
}
for ( int j = pre + 1; j <= n; j ++ )
rev_edge[i].push_back(j);
}
for ( int i = 1; i <= T; i ++ )
{
for ( int j = 1; j <= k; j ++ )
{
for ( auto v : edge[point[i][j]] )
{
is_edge[j][v] |= 1u << i - 1;
}
}
}
for ( int i = 1; i <= T; i ++ )
{
memset(f, 0, sizeof(f));
f[0][0] = 1.0;
for ( int j = 1; j <= k; j ++ )
{
for ( int w = 0; w <= s; w ++ )
{
f[j][w] += f[j - 1][w] * rev_edge[point[i][j]].size();
f[j][w + 1] += f[j - 1][w] * edge[point[i][j]].size();
}
}
sum[i] = f[k][s];
total += sum[i];
}
if ( total < 1 )
{
printf("0\n");
return 0;
}
for ( int i = 1; i <= T; i ++ )
{
int p = k * k * 10000 * sum[i] / total;
memset(f, 0, sizeof(f));
f[0][0] = 1.0;
for ( int j = 1; j <= k; j ++ )
{
for ( int w = 0; w <= s; w ++ )
{
f[j][w] += f[j - 1][w] * rev_edge[point[i][j]].size();
f[j][w + 1] += f[j - 1][w] * edge[point[i][j]].size();
}
}
while ( p -- )
{
double val = floor(Sdouble(1.0, sum[i] + 0.99999));
int now = s;
bool flag = false;
for ( int j = k; j >= 1; j -- )
{
if ( f[j - 1][now] * rev_edge[point[i][j]].size() >= val )
{
sp[j] = rev_edge[point[i][j]][(int)( ( val - 1 ) / f[j - 1][now] )];
val -= (int)( ( val - 1 ) / f[j - 1][now] ) * f[j - 1][now];
}
else
{
if ( !now )
{ flag = true; break; }
val -= f[j - 1][now] * rev_edge[point[i][j]].size();
sp[j] = edge[point[i][j]][(int)( ( val - 1 ) / f[j - 1][now - 1] )];
val -= (int)( ( val - 1 ) / f[j - 1][now - 1] ) * f[j - 1][now - 1];
--now;
}
}
if ( flag )
continue;
for ( int j = 1; j <= 32; j ++ )
matrix[j - 1] = is_edge[j][sp[j]];
for ( int bit = 0; bit < 5; bit ++ )
{
for ( int j = 0; j < 32; j ++ )
tmp[j] = matrix[j];
unsigned int x = 0, y = 0;
for ( int j = 0; j < 32; j ++ )
{
if ( j >> bit & 1 )
x |= 1u << j;
else
y |= 1u << j;
}
for ( int j = 0; j < 32; j += 1 << bit + 1 )
{
for ( int w = 0; w < 1 << bit; w ++ )
{
matrix[j + w] = ( ( tmp[j + w] & y ) | ( tmp[j + ( 1 << bit ) + w] & y ) << ( 1 << bit ) );
matrix[j + ( 1 << bit ) + w] = ( ( tmp[j + w] & x ) >> ( 1 << bit ) | ( tmp[j + ( 1 << bit ) + w] & x ) );
}
}
}
int match = 0;
for ( int j = 0; j < 32; j ++ )
match += __builtin_popcount(matrix[j]) == s;
if ( match )
{
ans += 1.0 / match;
++cnt;
}
}
}
ans = ans * total / cnt;
printf("%.8lf\n", ans);
return 0;
}