Atcoder abc251

發表於 更新於 分類於 ， Disqus： 文章字數： 3.2k 所需閱讀時間 ≈ 11 分鐘
G(计算几何)Ex(数论,排列组合)

https://atcoder.jp/contests/abc251/tasks

G - Intersection of Polygons

N点 凸convex多边形

按照逆向时针给点

考虑 m个 n点凸多边形

第i个,是通过把原来的平移(ui,vi)

q个询问, 问(ai,bi) 是否被所有m个凸多边形覆盖

范围

n 50

m 2e5

q 2e5

x,y,u,v,a,b [-1e8,1e8]

2s

1024mb

我的思路

两个方向

  1. 把m个的交算出来, 然后查询,

  2. 对m个偏移量算偏移量的凸包, 每个Q去找 最差的叠加?

因为一个凸包 沿着(ui,vi) 移动后的交

= 这个凸包与 (ui/2,vi/2), (ui,vi) 的交

因此无限划分

所以 等于平移过程中所有的交

所以对于m个平移量也可以求凸包

也就是原图形 与一个凸包内的向量集的偏移的叠加图怎么求

而实际上凸包从线性规划角度看,就是 边的数量个不等式, 而平移的话就是每边的沿着法线方向最大的偏移量

所以也是得到 n(50) 个 不等式, 不再去求交,而直接用不等式

最后每个q就暴力求就完了?

然后似乎m也不需要求凸包,直接枚举所有就行,因为内部的不会产生贡献

代码

https://atcoder.jp/contests/abc251/submissions/35205904

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

vector<pair<ll,ll> >xy;
vector<pair<ll,ll> >uv;
vector<tuple<ll,ll,ll>> ineq; // ax+by+c >= 0

int main(){
  int n = read();
  rep(i,0,n) xy.push_back({read(),read()});
  rep(i,0,n){
    auto [x1,y1] = xy[i];
    auto [x0,y0] = xy[(i+1)%n];
    ineq.push_back({y1-y0,-(x1-x0),y0*(x1-x0) - x0*(y1-y0)}); // (x-x0,y-y0) x (x1-x0,y1-y0) >= 0
  }
  int m = read();
  rep(i,0,m) uv.push_back({read(),read()});
  rep(i,0,n) {
    auto [a,b,c] = ineq[i]; // ax+by+c >= 0
    ll inc = 0x3f3f3f3f3f3f3f3f;
    for(auto [u,v]:uv) inc = min(inc, -u*a -v*b);
    ineq[i] = {a,b,c+inc};
  }

  int q = read();
  while(q--){
    ll x = read();
    ll y = read();
    bool ok = true;
    for(auto [a,b,c]:ineq) ok = ok && (a*x+b*y+c >= 0);
    printf("%s\n", ok?"Yes":"No");
  }
  return 0;
}

Ex - Fill Triangle

第i行 有i个块, 形成三角形(?????为啥是column, 我看了半天 , column英文不是列吗, 迷惑

例如

1
2
3
4
5
6
     3
    5 5
   5 0 5
  1 4 3 2
 4 4 0 3 6
2 2 2 5 5 1

给定一个压缩后的长m的序列 p = {ai,ci}, 它表示一个原始序列A, 比如 (a=2,c=3) 表示原序列中连续的3个2

最后一行 就是Ai

其它的每个数 = 正下方与右下方的和 mod 7, ([i][j] = [i+1][j] + [i+1][j+1](mod 7)

现在问, 第k行的内容

范围

n 1e9

m 200

k 5e5

ai [0,6]

ci >= 1

sum ci = n

4s

1024mb

我的思路

这就是 给定三角形最后一行, 问第k行, 然后每个元素等于下面 两个位置的和

这暴力算就n^2, 然而连n都接受不了, 注意到m=200, 有没有可能就一直用压缩的表示?

但即使可行也是O(m n)

而且,每次相邻不同会产生1个新的段,所以也很容易膨胀, 所以还不可能持续是m

假设不把它三角形, 去掉i和j的大小限制, 会发现第i行 不过是截取前面i个数而已, 因为超过i的部分也一直不会影响内部

所以这其实等于 最终行 做(n-k) 次矩阵乘法, 然后得到的前k个数

但矩阵似乎太大了

再就是直接算, 那么就是 计算最后一排的每个数对当前的贡献

而贡献次数,其实就是路径数

那么就是最有一排 [j0..j1] 到j的贡献是

sum binom(n-k,j-j0) + … +binom(n-k,j-j1)

题解

!!!!! 核心在 mod 7

首先看看 binom(p^k,n) mod p

要证明$\binom{p^k}{i} = 0 \pmod p$, 当$i\ne 0,i\ne p^k$时

即要证明$(x+1)^{p^k} \equiv x^{p^k} + 1 \pmod p,k>0$

注意这里不只表示mod相等, 还表示着对系数的mod 的消除, 因为如果只是要相等的话, 费马小定理就能推出来, 但费马小定理 并没有 系数mod p为0的意义

proof

k=1时 根据binom的表达式分母没有包含p因子的, 得证

归纳法,若k成立, 则k+1成立

$(x+1)^{p^{m+1}} \equiv ((x+1)^{p^m})^p \equiv (x^{p^m} + 1)^p \equiv x^{p^{m+1}} + 1 \pmod p$

得证

lucas 定理

如果把n和k按照p的幂次 乘系数和展开的话

$n = a_r p^r + \cdots + a_1 p + a_0$

$k = b_r p^r + \cdots + b_1 p + b_0$

那么有 $\binom{n}{k} \equiv \prod_{i=0}^r \binom{a_i}{b_i} \pmod p.$

proof

$\begin{aligned}
&\binom{n}{k} \\
&\equiv [x^k] (1+x)^n \\
&\equiv [x^k] (1+x)^{a_r p^r + \cdots + a_1 p + a_0} \\
&\equiv [x^k]\prod_{i=0}^r ((1+x)^{p^i})^{a_i} \\
&\equiv [x^k]\prod_{i=0}^r (1 + x^{p^i})^{a_i} \\
&\equiv [x^{b_r p^r + \cdots + b_1 p + b_0}]\prod_{i=0}^r (1 + x^{p^i})^{a_i} \\
&\equiv \prod_{i=0}^r [x^{p^i b_i}](1 + x^{p^i})^{a_i}\\
&\equiv \prod_{i=0}^r \binom{a_i}{b_i}.
\end{aligned}$

这里用了基本的binom, 上面证明的表达式, 以及按p进制拆分

什么? lucas定理在日本的大学入学考试很常见?

比如 mod2 + lucas定理 = Sierpiński triangle

回到原题

看$B_{i,j}$ 向下 7^k 大小的三角形, 根据第一个证明的结论 有表达式

$B_{i,j} \equiv B_{i+7^k,j} + B_{i+7^k,j+7^k} \pmod{7}$

所以可以算出 [k~n-(n-k)/7] 中的某一行, (n-7t < k < n - t, t > (n-k)/7)

然后log级别 向上 算出到[k~k+7) 中的某一行, 然后暴力算出这些即可

所以这里也不能直接暴力, 因为n-(n-k)/7 也会很大

不过好在m 最大200, 可以考虑连续一段相同的 去处理, 这样一次操作后是最多2m段, 因为相当于双指针等间距向右侧移, 而每次一个到头为一段, 那么最多出现2m次到头

1
2
3
4
5
6
7
8
9
10
11
n = 10**9
m = 200
s = 0
while m < n:
    d = n//7
    for i in range(6):
        n-=d
        s+=min(n,m)
        m*=2

print(s)

s只有21853356, 这时n=2915452

而m > n 时,每次就是n,而显然n log n级别,

另一个方法 使用lucas定理

$B_{K,s} = \sum_{i=0}^{N-K} A_{s+i} \binom{N-K}{i}$

就是上面 我得到的表达式, 但是具体计算是用 lucas 来解决 范围和

代码

https://atcoder.jp/contests/abc251/submissions/35208614

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint=atcoder::static_modint<7>;
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}

template<class T>
T f(const T &ac, int X) {
  auto norm=[&](int &i,int &c){ while(i<(int)ac.size() && c>=ac[i].second) c-=ac[i++].second;};

  int li=0; // ac index
  int lc=0; // count
  int ri=0; // ac index
  int rc=0; // count
  vector<pair<mint,int> > res;
  for(norm(ri,rc+=X);ri!=(int)ac.size();) {
    auto [lv,ls]=ac[li];
    auto [rv,rs]=ac[ri];
    mint val=lv+rv;
    int len=min(ls-lc,rs-rc); // 相同的一段, 不要len=1
    res.push_back({val,len});
    norm(li,lc+=len);
    norm(ri,rc+=len);
  }
  return res;
}

int main() {
  int N=read();
  int M=read();
  int K=read();
  vector<pair<mint,int> >ac;
  rep(i,0,M) ac.push_back({read(),read()});

  int n=N;
  int x=282475249; // 7**10 < 10**9 < 7**11
  while(n>K){
    while(x>n-K)x/=7;
    ac=f(ac,x);
    n-=x;
  }
  for(auto [k,v]:ac)while(v--)printf("%d ",k.val());
}

附一个 mod7的组合数

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
0 [1]
1 [1, 1]
2 [1, 2, 1]
3 [1, 3, 3, 1]
4 [1, 4, 6, 4, 1]
5 [1, 5, 3, 3, 5, 1]
6 [1, 6, 1, 6, 1, 6, 1]
7 [1, 0, 0, 0, 0, 0, 0, 1]
8 [1, 1, 0, 0, 0, 0, 0, 1, 1]
9 [1, 2, 1, 0, 0, 0, 0, 1, 2, 1]
10 [1, 3, 3, 1, 0, 0, 0, 1, 3, 3, 1]
11 [1, 4, 6, 4, 1, 0, 0, 1, 4, 6, 4, 1]
12 [1, 5, 3, 3, 5, 1, 0, 1, 5, 3, 3, 5, 1]
13 [1, 6, 1, 6, 1, 6, 1, 1, 6, 1, 6, 1, 6, 1]
14 [1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1]
15 [1, 1, 0, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 1, 1]
16 [1, 2, 1, 0, 0, 0, 0, 2, 4, 2, 0, 0, 0, 0, 1, 2, 1]
17 [1, 3, 3, 1, 0, 0, 0, 2, 6, 6, 2, 0, 0, 0, 1, 3, 3, 1]
18 [1, 4, 6, 4, 1, 0, 0, 2, 1, 5, 1, 2, 0, 0, 1, 4, 6, 4, 1]
19 [1, 5, 3, 3, 5, 1, 0, 2, 3, 6, 6, 3, 2, 0, 1, 5, 3, 3, 5, 1]
20 [1, 6, 1, 6, 1, 6, 1, 2, 5, 2, 5, 2, 5, 2, 1, 6, 1, 6, 1, 6, 1]
21 [1, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 1]
22 [1, 1, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 1, 1]
23 [1, 2, 1, 0, 0, 0, 0, 3, 6, 3, 0, 0, 0, 0, 3, 6, 3, 0, 0, 0, 0, 1, 2, 1]
24 [1, 3, 3, 1, 0, 0, 0, 3, 2, 2, 3, 0, 0, 0, 3, 2, 2, 3, 0, 0, 0, 1, 3, 3, 1]
25 [1, 4, 6, 4, 1, 0, 0, 3, 5, 4, 5, 3, 0, 0, 3, 5, 4, 5, 3, 0, 0, 1, 4, 6, 4, 1]
26 [1, 5, 3, 3, 5, 1, 0, 3, 1, 2, 2, 1, 3, 0, 3, 1, 2, 2, 1, 3, 0, 1, 5, 3, 3, 5, 1]
27 [1, 6, 1, 6, 1, 6, 1, 3, 4, 3, 4, 3, 4, 3, 3, 4, 3, 4, 3, 4, 3, 1, 6, 1, 6, 1, 6, 1]
28 [1, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 1]
29 [1, 1, 0, 0, 0, 0, 0, 4, 4, 0, 0, 0, 0, 0, 6, 6, 0, 0, 0, 0, 0, 4, 4, 0, 0, 0, 0, 0, 1, 1]
30 [1, 2, 1, 0, 0, 0, 0, 4, 1, 4, 0, 0, 0, 0, 6, 5, 6, 0, 0, 0, 0, 4, 1, 4, 0, 0, 0, 0, 1, 2, 1]
31 [1, 3, 3, 1, 0, 0, 0, 4, 5, 5, 4, 0, 0, 0, 6, 4, 4, 6, 0, 0, 0, 4, 5, 5, 4, 0, 0, 0, 1, 3, 3, 1]
32 [1, 4, 6, 4, 1, 0, 0, 4, 2, 3, 2, 4, 0, 0, 6, 3, 1, 3, 6, 0, 0, 4, 2, 3, 2, 4, 0, 0, 1, 4, 6, 4, 1]
33 [1, 5, 3, 3, 5, 1, 0, 4, 6, 5, 5, 6, 4, 0, 6, 2, 4, 4, 2, 6, 0, 4, 6, 5, 5, 6, 4, 0, 1, 5, 3, 3, 5, 1]
34 [1, 6, 1, 6, 1, 6, 1, 4, 3, 4, 3, 4, 3, 4, 6, 1, 6, 1, 6, 1, 6, 4, 3, 4, 3, 4, 3, 4, 1, 6, 1, 6, 1, 6, 1]
35 [1, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 1]
36 [1, 1, 0, 0, 0, 0, 0, 5, 5, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 5, 5, 0, 0, 0, 0, 0, 1, 1]
37 [1, 2, 1, 0, 0, 0, 0, 5, 3, 5, 0, 0, 0, 0, 3, 6, 3, 0, 0, 0, 0, 3, 6, 3, 0, 0, 0, 0, 5, 3, 5, 0, 0, 0, 0, 1, 2, 1]
38 [1, 3, 3, 1, 0, 0, 0, 5, 1, 1, 5, 0, 0, 0, 3, 2, 2, 3, 0, 0, 0, 3, 2, 2, 3, 0, 0, 0, 5, 1, 1, 5, 0, 0, 0, 1, 3, 3, 1]
39 [1, 4, 6, 4, 1, 0, 0, 5, 6, 2, 6, 5, 0, 0, 3, 5, 4, 5, 3, 0, 0, 3, 5, 4, 5, 3, 0, 0, 5, 6, 2, 6, 5, 0, 0, 1, 4, 6, 4, 1]
40 [1, 5, 3, 3, 5, 1, 0, 5, 4, 1, 1, 4, 5, 0, 3, 1, 2, 2, 1, 3, 0, 3, 1, 2, 2, 1, 3, 0, 5, 4, 1, 1, 4, 5, 0, 1, 5, 3, 3, 5, 1]
41 [1, 6, 1, 6, 1, 6, 1, 5, 2, 5, 2, 5, 2, 5, 3, 4, 3, 4, 3, 4, 3, 3, 4, 3, 4, 3, 4, 3, 5, 2, 5, 2, 5, 2, 5, 1, 6, 1, 6, 1, 6, 1]
42 [1, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 1]
43 [1, 1, 0, 0, 0, 0, 0, 6, 6, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 6, 6, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 6, 6, 0, 0, 0, 0, 0, 1, 1]
44 [1, 2, 1, 0, 0, 0, 0, 6, 5, 6, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 6, 5, 6, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 6, 5, 6, 0, 0, 0, 0, 1, 2, 1]
45 [1, 3, 3, 1, 0, 0, 0, 6, 4, 4, 6, 0, 0, 0, 1, 3, 3, 1, 0, 0, 0, 6, 4, 4, 6, 0, 0, 0, 1, 3, 3, 1, 0, 0, 0, 6, 4, 4, 6, 0, 0, 0, 1, 3, 3, 1]
46 [1, 4, 6, 4, 1, 0, 0, 6, 3, 1, 3, 6, 0, 0, 1, 4, 6, 4, 1, 0, 0, 6, 3, 1, 3, 6, 0, 0, 1, 4, 6, 4, 1, 0, 0, 6, 3, 1, 3, 6, 0, 0, 1, 4, 6, 4, 1]
47 [1, 5, 3, 3, 5, 1, 0, 6, 2, 4, 4, 2, 6, 0, 1, 5, 3, 3, 5, 1, 0, 6, 2, 4, 4, 2, 6, 0, 1, 5, 3, 3, 5, 1, 0, 6, 2, 4, 4, 2, 6, 0, 1, 5, 3, 3, 5, 1]
48 [1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1]
49 [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

总结

G

啊 又过橙题了

Ex

数论

组合数与模运算

Lucas’s theorem

参考

官方题解

Sierpiński triangle