Atcoder agc039

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
C (math + inclusion-exclusion),D(平面几何)

C

大意

求sum{f(x)},x取值为 [0,X]的所有

其中f(x) = x以N位二进制表示(x<2^N,不足的补前导零),把最右的二进制位 取反 放到最左，这样操作?次后变回原样

结果mod 998244353

数据范围

1<=N<=200000

0<X<2^N

2s

1024MB

例

N=5 x=3时

00110 -> 10011 -> 01001 -> 00100 -> 10010 -> 11001 -> 01100 -> 10110 -> 11011 -> 01101 -> 00110

f(3) = 10

题解

显然2N次一定能回到原来的数

又假设 循环节最小为k，那么一定所有循环节为k的倍数，所以2N一定是k的倍数

又N次移动一定是何原来所有位取反 一定不相等

所以2N/k 一定是奇数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[xxxxxxxxxxxxxxxxxx]
[移动k][xxxxxxxxxxxxxxxxxx]

[ 长度 N                ][        原字符串取反N ]
[ 长度 2N                                       ]
[长度k][长度k][长度k][长度k][长度k][长度k][长度k]
       [长度k][长度k][长度k][长度k][长度k][长度k][长度k]
                        |这里k是偶数 刚好对半分

[长度k               ]
[长k后一半][长k前一半] 取反

所以 [长度k] = [长度k前一半] + [长度k前一半]取反

所以可行串又可以看做

[串A][~串A][串A][~串A][串A][~串A]...[串A][~串A][串A]

然后容斥 枚举k

时间复杂度 = O(N * N因数个数+ N log(N) )

我们把上面 串A 的长度 定义为循环节长度

容斥的部分

先假设所有的循环都是2n,那么 答案为(X+1)*(2n)%MOD

假设长度len循环节有f(len)个可行方案，那么对答案的变化为 +f(len)*(len-2n)%MOD

容斥原理 len的 权重为 = (len-2n) - ans(len的2次以上倍数)

h(len) = len-2n - sum{h(k * len)}, 其中k>=2且 长度k*len 可行

代码

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

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

char s[200010];
int n;
int ans;
int val[200010]; // val[i]表示以 i为循环节长度的方案数
vector<int>divs; // 所有 2n/2divs[idx] 为奇数


// 以 s[0..len-1]为 循环节 [正][取反][正]这样产生的长n的字符串的 方案数
ll cnt(int len) {
  int ans = 0;
  rep(i,0,len){
    ((ans*=2)+=s[i]-'0')%=MOD;
  }
  // [0.........................n]
  // [0...len][反0...len][0...len]
  // s>=t ans+1
  // t>s ans+1
  // 因为统计了全零所以+1, 如果t比s大那么[0..len]作为循环节不行,把 [0..len] 值减1可行 所以 全零+1,再-1就是ans
  rep(i,0,n){
    char ti = ((s[i%len]-'0')^((i/len)%2))+'0';
    if (s[i] > ti) return ans + 1;
    if (ti > s[i]) return ans;
  }
  return ans + 1;
}

int main() {
  cin>>n;
  scanf("%s", s);
  rep(i,1,n+1){
    if (n % i == 0 && (n / i) % 2 == 1){
      divs.pb(i);
    }
  }
  ll ans = cnt(n) * (2 * n) % MOD; // 全部都是2n 次
  per(idx,0,divs.size()){
    int i = divs[idx];
    val[i] = (2*i-2*n) % MOD;
    rep(j,idx+1,divs.size()){
      if(divs[j] % divs[idx] == 0){
        (val[i]-=val[divs[j]])%=MOD;
      }
    }
    (ans += cnt(i) * val[i] )%=MOD;
  }
  cout<<(ans+MOD)%MOD<<endl;
  return 0;
}

D

大意

到(0,0) 长度为1上的一系列点

随机选这些点形成的三角形的内切圆的圆心期望坐标

数据范围

圆上点的个数<=3000

4s

1024MB

题解

https://codeforces.com/blog/entry/70291 不少人吐槽 觉得这是 数学奥林匹克的题

假设选的三角形为$\Delta ABC$,做三个角的角平分线分别交$\Delta ABC$ 外接圆于点$A_1,B_1,C_1$

因为是角平分线所以显然，角平分线的交点就是要求的内心

$A_1,B_1,C_1$分别为$\widehat{BC},\widehat{CA},\widehat{AB}$的中点 (圆周角知识)

假设圆周上点的顺序为$A,C_1,B,A_1,C,B_1$

下面证明$\Delta ABC$的角平分线是，$\Delta A_1B_1C_1$的垂线

对称性只需要证明 $AA_1 \perp B_1C_1$

$\angle AC_1B_1+\angle A_1AC_1$

$= \angle ABB_1+\angle A_1AB+\angle BCC_1$

$= (\angle ABC+\angle CAB+\angle BCA)/2$

$= 90^\circ$

综上$\Delta ABC$的内心为 $\Delta A_1B_1C_1$的垂心

$A_1B_1C_1$的外接圆也是单位圆所以$A_1B_1C_1$的外心为$(0,0)$

假设$\Delta ABC$的 外心 垂心 重心分别为$O,H,G$

下面证明欧拉线 即 $3\cdot\vec{OG} = \vec{OH}$

即$O,H,G$三点共线且 分割线段长度为 $1:2$

注意到 $\vec {GA} = \frac{\vec {BA}+\vec {CA}}{3}$

所以有 ${\displaystyle {\vec {GA}}+{\vec {GB}}+{\vec {GC}}=0.}$

$3\cdot \vec{OG}$

$= (\vec{OA}+\vec{AG}) + (\vec{OB} + \vec{BG}) + (\vec{OC} + \vec{CG})$

$= \vec{OA}+\vec{OB} + \vec{OC} + (\vec{AG}+\vec{BG}+\vec{CG})$

$= \vec{OA}+\vec{OB}+\vec{OC}$

注意到

$(\vec{OA}+\vec{OB}+\vec{OC}-\vec{OH})\cdot \vec{BC}$

$=(\vec{OA}-\vec{OH})\cdot \vec{BC} +(\vec{OB}+\vec{OC})\cdot \vec{BC}$

$=\vec{HA}\cdot \vec{BC} +(\vec{OB}+\vec{OC})\cdot \vec{BC}$

$=0$

因为HA垂线所以前一半0

因为$O$为外心，所以$\Delta OBC$是以$BC$为底的等腰三角形 所以 后一半乘积为0

然后又因为$\vec{BC}\neq 0$ 所以有 $\vec{OA}+\vec{OB}+\vec{OC} = \vec{OH}$

综上$3\cdot\vec{OG} = \vec{OH}$ 欧拉线得证

重心坐标就没啥好说了 三角形顶点的均值

所以 内心期望 = 弧的中点 的 均值

注意这样算的是 内心 根据上面的外心 垂心关系，把内心坐标乘3就行了

要注意的是 弧的中点 不是靠优弧和劣弧来决定的 而是 弧外的第三个点不在的那条弧上

时间复杂度 O(点^2)

代码

卧槽 这还会有精度问题

精度问题代码

AC代码

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 INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
int n;
int l;
 
pair<double,double> twoT2P(int twoT){
  double v = pi*twoT/l;
  return make_pair(cos(v),sin(v));
}
int t[3010];
 
int main(){
  cin>>n>>l;
  rep(i,0,n){
    scanf("%d",t+i);
  }
  double cntX=0;
  double cntY=0;
  rep(i,0,n){
    rep(j,i+1,n){
      pair<double,double> ret = twoT2P(t[i]+t[j]);
      cntX+=(n-2*(j-i))*ret.first;
      cntY+=(n-2*(j-i))*ret.second;
    }
  }
 
  printf("%.15lf %.15lf\n",6*cntX/n/(n-1)/(n-2),6*cntY/n/(n-1)/(n-2));
  return 0;
}