SRM 545 div1 hard SetAndSet

\(n\le50\) 个数 \(V\le2^{20}\),要分成非空的两组,使得对每组把所有数 \(\And\) 起来结果相同。求方案数。


首先分位,对于全 \(0/1\) 的位,随便分直接无视。此外就一定有 \(0\) 了,所以必然是两个集合结果都为 \(0\)。(之前居然想半天没想到这一点,反省……)

然后就可以转化成,两个集合必须都要有 \(0\),发现这个不好做,但是反面很好做,所以考虑容斥。

容斥就要对给定的一些位不合法,不合法意味着 \(0\) 全去了某一边。所以在考虑多个位时,就是关于 \(0\) 有交集的两个位都必须一起划分。

然后用 UFS 合并统计就好了。

Gym 101987G Secret Code

实数区间 \([0,S\le1000]\) 上均匀随机三条线段的开始点,长度分别固定是 \(w_1,w_2,w_3\),问:随机后,线段从左到右,第一条和第二条相交,第二条和第三条相交的概率。


反正是实数,就先考虑写个积分的式子看看。

\[ \int_0^S \mathrm dl_1\int_{l_1}^{\min(l_1+w_1,S)}\mathrm dl_2\min(S-l_2-w_2,w_2) \]

额,也不算很复杂……主要是,反正数值积分那么快,我何必操心它到底啥样呢.jpg

当然,这个东西完全是分段线性的,而且形式摆在那儿了,我们不妨想想怎么直接求。

先考虑 \(l_1-l_2\) 平面,添个纵轴 \(l_3\) ,我们看看哪些点是合法的。

对于前俩轴我们先想个范围,也就是这里积分上下限的限制,显然就是一个斜着的梯形。

而第三条线段只需和第二条相交,也就是说只和 \(l_2\) 有关,又是什么形状呢?还是个梯形 =、= 毕竟限制都是类似的。所以本质其实就是求俩四棱柱(底面是梯形,摆放方向互相垂直)的交的体积。

如图所示,右上角是左边立体图的右视图,分别考虑 \(S_1,S_2\) 两块对应的体积。

\(S_1\) 是个平行四边形,很好办,对应的左边棱柱是个直角三棱锥,也就是说关于 \(l_2\) 是线性的,所以我们可以直接底面积乘高除以二,也就是 \(w_1w_2\cdot\frac{w_1}2\) 这项。

\(S_2\) 是个梯形,看上去比较棘手,但是它对应的棱柱是个等高的东西,就是右视图上某一点对应的体积上的最高点和最低点的高度差是一定的,根据基础几何知识我们知道可以直接用这个高度差乘以底面积。底面积可以补成平行四边形减去一个等腰直角三角形,所以这部分贡献就是 \([(S-w_1)w_2-\frac12w_2^2]w_1\) 这项。

整理一下就得到答案是 \(w_1w_2\left(S-\frac{w_1+w_2}{2}\right)\),简单吧!别忘了考虑全排列嗷!可以枚举俩然后乘二计算。

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
// 静かな海
#include <bits/stdc++.h>
#define dbg(x, y...) fprintf(stderr, x, y)
#define pline() (dbg("Passing Line #%d in Func [%s]", __LINE__, __FUNCTION__))
using namespace std;

inline int rd() {
int x=0,c,f=1;while(!isdigit(c=getchar()))if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=x*10+c-'0';return x*f;
}
const int N = 2e6+3;

double w[5];
vector<pair<double, int>> v;

signed main() {
int n = rd();
for (int i=1; i<=n; i++) {
scanf("%lf%lf%lf%lf", w+4, w+1, w+2, w+3);
w[0] = 0;
for (int j=1; j<=3; j++)
for (int k=j+1; k<=3; k++)
w[0] += (2*w[4]-w[j]-w[k])*w[j]*w[k];
v.emplace_back(w[0]/w[4]/w[4]/w[4], i);
}
sort(v.begin(), v.end());
for (auto& x:v) printf("%d ", x.second);
}

易燃易爆杂题

构造一个正整数集合 \(S\subset [4n]:|S|=n\)\(S\) 里每两个元素不互质但不整除。

qwq先想想试试?


= = 假如你和我一样在那里考虑素因子,那就面壁思过去(

\(S=\{2n+2,2n+4,\cdots,4n\}\)

这应该是对于 \(n>1\) 的唯一解。

我太菜了,orzzz易燃

感觉多想一会儿应该能想到的,自己还是太浮躁,而且不擅长应付这类“师出无名”的构造。

什么时候再找 ATC 练练吧。

整点计数 cz_xuyixuan 2019

回来读 19 年集训队论文,没想到发现 xyx 写了以前一个令我印象深刻的题目的超级加强版的命题报告。

关键在于 \(a^2+b^2\) 的高斯整数分解 \((a+b\mathrm i)(a-b\mathrm i)\) ,这样的分解在不考虑乘上一些 \(\omega_4^k\) 的因子的时候是唯一的,于是加法变成了乘法!

咳咳,在 3b1b 找到了这个解法,要看前半部分不如直接看视频吧。

后半部分就是一个积性函数求和,用 \(\min25\) 筛或洲阁筛解决。