LibreOJ 3056 「HNOI2019」多边形

发表于 | 分类于 | 3

还是比较小清新的一道题？我甚至找不到合适的标签（

显然终止条件就是所有边连向 n，最优策略也是每次把一条边连向 n。
所以最少次数就是开始时不与 n 相连的边的条数。

那么把和 n 相连的点（包括 1,n−1）排序后，取相邻的两个点 l,r，则必然存在，且仅存在一个点 mid∈(l,r) 与 l,r 都相连。
那么如果进行了 (l,r)「旋转」便相当于把 (l,r) 拆成了 (l,mid),(mid,r)。
然后这样就能建出一片二叉树森林，方案数便是合并左右儿子的贡献，组合数算一下就行了。

考虑在此基础上再进行一次 (a,b)「旋转」操作会有什么情况：

  • (a,b) 不是某棵二叉树的根。
    那么这次操作并不是最优策略，不会影响步数。 而在二叉树上，相当于把 (a,b) 对应的点进行一次类似平衡树的旋转操作。
    注意到 a<b，并且 a 一定和 n 相连（若 a,b 都不与 n 相连则不合法），所以 (a,b) 一定是左儿子。
    计算此对答案的修改量并不难。
  • (a,b) 是某棵二叉树的根。 那么这会使步数减少一，并把一棵二叉树的根的左右子树拆开。
    这也不难计算。

代码： 

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <vector>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
const int N = 1e5;
const int mod = 1e9 + 7;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int W,n,m;
int fac[N + 5],ifac[N + 5];
int cnt,sum = 1,ans1,ans2;
vector<int> e[N + 5];
inline int C(int n,int m)
{
    return n < m ? 0 : (long long)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
inline int Ci(int n,int m)
{
    return n < m ? 0 : (long long)ifac[n] * fac[m] % mod * fac[n - m] % mod;
}
tr1::unordered_map< int,tr1::unordered_map<int,int> > id;
int fa[N + 5],ls[N + 5],rs[N + 5],sz[N + 5],rt;
void build(int &p,int l,int r)
{
    static int tot = 0;
    if(r - l == 1)
        return ;
    id[l][r] = p = ++tot;
    int mid = *upper_bound(e[r].begin(),e[r].end(),l);
    build(ls[p],l,mid),build(rs[p],mid,r),
    ls[p] && (fa[ls[p]] = p),
    rs[p] && (fa[rs[p]] = p),
    sz[p] = sz[ls[p]] + 1 + sz[rs[p]],
    sum = (long long)sum * C(sz[p] - 1,sz[ls[p]]) % mod;
}
int main()
{
    scanf("%d%d",&W,&n),fac[0] = 1;
    for(register int i = 1;i <= n;++i)
        fac[i] = (long long)fac[i - 1] * i % mod;
    ifac[n] = fpow(fac[n],mod - 2);
    for(register int i = n;i;--i)
        ifac[i - 1] = (long long)ifac[i] * i % mod;
    int u,v;
    for(register int i = 1;i <= n - 3;++i)
        scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
    for(register int i = 1;i <= n;++i)
        e[i].push_back(i % n + 1),e[i % n + 1].push_back(i);
    for(register int i = 1;i <= n;++i)
        sort(e[i].begin(),e[i].end());
    for(register vector<int>::iterator i = e[n].begin(),j = i + 1;j != e[n].end();++i,++j)
        rt = 0,build(rt,*i,*j),sum = (long long)sum * C(cnt += sz[rt],sz[rt]) % mod;
    printf("%d%c",cnt,"\n "[W]),W && printf("%d\n",sum);
    for(scanf("%d",&m);m;--m)
    {
        scanf("%d%d",&u,&v),ans1 = cnt,ans2 = sum;
        int p = id[u][v];
        if(fa[p])
            ans2 = (long long)ans2 * Ci(sz[p] - 1,sz[ls[p]]) % mod * Ci(sz[fa[p]] - 1,sz[p]) % mod,
            ans2 = (long long)ans2 * C(sz[rs[p]] + sz[rs[fa[p]]],sz[rs[p]]) % mod * C(sz[p] + sz[rs[fa[p]]],sz[ls[p]]) % mod;
        else
            --ans1,
            ans2 = (long long)ans2 * Ci(sz[p] - 1,sz[ls[p]]) % mod * Ci(cnt,sz[p]) % mod,
            ans2 = (long long)ans2 * C(cnt - sz[rs[p]] - 1,sz[ls[p]]) % mod * C(cnt - 1,sz[rs[p]]) % mod;
        printf("%d%c",ans1,"\n "[W]),W && printf("%d\n",ans2);
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment