欣闻 UOJ 已经用上了新 GCC,安排上了 C++20,我便拿出之前玩耍 MSVC 时写的 FFT 板子,改了改一些地方,交交试试。

结果上比较顺利,我觉得至少里面用上的 Concepts 和各类编译期求值计数还是有一定参考价值,并且这份 FFT 的优点还是比较明显的:

  • 包含一个 ModInt 类,作用如其名,模板参数是数字类型和模数。支持模意义下需要的各类运算符(位运算和大小比较自然无意义就没写了)和流输入输出;
  • 包含一个 FFT 类,用于做 DFT 和 IDFT,模板参数是数组元素类型,目前支持两种:ModInt<A,B>std::complex<double>,分别对应 NTT 和 FFT。不需要指定,自动根据模板参数选择算法;
  • NTT 不用自己找模数,在编译期能自动求出最小的原根来使用,找不到原根会报错;
  • 所有的非法模板参数都会在编译期较友好地提示,NTT模数对应的长度被超出时也会在运行期出错,理所当然地,用了 1e9+7 这类非 NTT 模数也是可以找出错误告诉你的;
  • 本来在 MSVC 上还用了 Modules 实现辅助计算类和变换类分离,现在提供 GCC 版本自然是删掉了。

缺点也是有一些的,直接列出来比较好

  • 最大的缺点,内部采用 std::vector 实现,速度较慢;
  • 采用工程和算法混合的阴间风格命名,部分地方比较混乱,如果你看的不爽可以自己改改。

具体来说,你可以在里面学习:

  • Concepts 的基本用法,require 套套套;
  • 简单 SFINAE 和 Type Traits;
  • Constexpr 求值,进阶:std::array 等;
  • If Constexpr 和 Static Assertion 并用,让 #define 从地球上消失的技巧;
  • 合理使用引用和重载减少大型数据复制。

这么些人人都会的技术。

没事啦,权当玩玩x

UOJ 34 提交记录:

FFT 好快啊,毕竟原数组值域只有 9 呢x

通用模板代码如下:

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
#include <iostream>
#include <vector>
#include <array>
#include <type_traits>
#include <complex>
#include <concepts>

namespace zmile {

template<class T>
concept GroupElement =
std::is_arithmetic_v<T>
|| requires(T x) { x = 1; x* x; };

template<class T>
concept BinaryPowerNumber = requires(T x) {
x >>= 1;
x & 1;
};

template<GroupElement ValueT, BinaryPowerNumber PowerT>
constexpr ValueT qpow(ValueT a, PowerT b, ValueT unit = 1) {
for (; b; b >>= 1, a = a * a)
if (b & 1) unit = unit * a;
return unit;
}

template <class ValueT = int, ValueT M = 998244353>
requires(std::is_integral_v<ValueT>&& M > 0 && requires(ValueT x) { x = M; })
class ModInt {
using ThisT = ModInt<ValueT, M>;
ValueT value;
public:
using value_t = ValueT;

constexpr ModInt() : value(0) { }
constexpr ModInt(ValueT value) : value((value % M + M) % M) { }
//constexpr ModInt(int64_t value) : value((value % M + M) % M) { }

inline constexpr explicit operator bool() const { return value; }

inline constexpr ThisT operator-(void) const { return (M - value) % M; }

inline constexpr ThisT operator+(const ThisT& rhs) const { return (value + rhs.value) % M; }
inline constexpr ThisT operator-(const ThisT& rhs) const { return *this + -rhs; }
inline constexpr ThisT operator*(const ThisT& rhs) const { return ValueT(1ull * value * rhs.value % M); }
inline constexpr ThisT operator/(const ThisT& rhs) const { return *this * qpow(rhs, M-2); }

inline constexpr ThisT& operator+=(const ThisT& rhs) { return *this = *this + rhs; }
inline constexpr ThisT& operator-=(const ThisT& rhs) { return *this = *this - rhs; }
inline constexpr ThisT& operator*=(const ThisT& rhs) { return *this = *this * rhs; }
inline constexpr ThisT& operator/=(const ThisT& rhs) { return *this = *this / rhs; }

inline constexpr bool operator==(const ThisT& rhs) const { return value == rhs.get_value(); }
inline constexpr bool operator==(const ValueT& rhs) const { return value == rhs; }

inline constexpr ThisT get_inv() const { return ThisT(1) / value; }
inline constexpr ValueT get_value() const { return value; }
};

template <class ValueT, ValueT M>
requires(std::is_integral_v<ValueT>&& M > 0 && requires(ValueT x) { x = M; })
std::ostream& operator<<(std::ostream& os, ModInt<ValueT, M> val)
{
return os << val.get_value();
}

template <class ValueT, ValueT M>
requires(std::is_integral_v<ValueT>&& M > 0 && requires(ValueT x) { x = M; })
std::istream& operator>>(std::istream& is, ModInt<ValueT, M>& val)
{
static ValueT temp_val;
is >> temp_val;
val = temp_val;
return is;
}

// requires mod is prime
template<auto mod>
requires(std::is_integral_v<decltype(mod)>
&& requires() { mod % mod; mod - mod; mod / mod; qpow(mod, mod); })
constexpr decltype(mod) find_primitive_root_internal() {
using ValueT = decltype(mod);
// this is enough for int64_t
constexpr int MAX_PRIME_FACTOR_COUNT = 17;
std::array<ValueT, MAX_PRIME_FACTOR_COUNT> fac{ 0 };
//std::vector<ValueT> fac;
auto vm = mod - 1; int pos = 0;
for (int x = 2; x * x <= vm; x++) {
if (vm % x == 0) {
fac[pos++] = x;
while (vm % x == 0) vm /= x;
}
}
if (vm != 1) fac[pos++] = vm;

for (auto ans = 2; ans < mod; ans++) {
bool failed = false;
for (auto x : fac) {
if (x == 0 || x == 1) break;
if (qpow<class ModInt<ValueT, mod>>(ans, (mod - 1) / x) == 1) {
failed = true;
break;
}
}
if (!failed) return ans;
}

return 0;
}

template <auto mod>
constexpr auto find_primitive_root() {
constexpr auto rt = find_primitive_root_internal<mod>();
static_assert(rt, "FATAL ERR: the primitive root doesn't exists!");
return rt;
}

// NTT max valid poly length
inline constexpr static auto get_max_valid_length(auto M) {
auto Mt = M; size_t cnt2 = 0;
while (!(Mt & 1))
Mt >>= 1, cnt2++;
return 1ull << cnt2;
}

}


namespace zmile {

template <class T>
struct is_modint : public std::false_type { };
template <class T, T M>
struct is_modint<ModInt<T, M>> : public std::true_type { };
template <class T>
constexpr bool is_modint_v = is_modint<T>::value;

template <class T>
struct get_modint_mod;
template <class T, T M>
struct get_modint_mod<ModInt<T, M>> {
static const T value = M;
};
template <class T>
constexpr auto get_modint_mod_v = get_modint_mod<T>::value;

template<class ValueT = ModInt<>>
requires(
requires(ValueT x) {
x + x;
x * x;
x / ValueT(10);
ValueT(1) / x;
x = 1;
}
)
class FFT {
size_t n;
std::vector<size_t> rev;
using poly_t = std::vector<ValueT>;
const double PI = std::acos(-1);

public:
FFT(size_t n = 0) {
if (n) set_size(n);
}

enum class TransformDirection : int8_t {
DFT = 1,
IDFT = -1
};

// set an enough length to STORE THE MULT RESULT
void set_size(size_t size) {
for (size_t L = 1; (n = L) <= size; L <<= 1);
rev.assign(n, 0);
for (size_t i = 1; i < n; i++)
rev[i] = rev[i >> 1] >> 1 | (n >> 1) * (i & 1);
}

inline poly_t transform(const poly_t& poly, TransformDirection dir) {
poly_t result;
transform(poly, result, dir);
return result;
}

// also work correctly when poly === result
inline void transform(const poly_t& poly, poly_t& result, TransformDirection dir) {
if (poly.empty()) return result.clear();

if (n < poly.size())
set_size(poly.size());

if (&result != &poly)
result = poly;
result.resize(n);
if constexpr (is_modint_v<ValueT>) {
if (get_max_valid_length(get_modint_mod_v<ValueT>-1) < n)
throw std::logic_error("FATAL ERR: the mod prime is not strong enough to hold the NTT result!");
}

for (size_t i = 0; i < n; i++) {
if (i < rev[i])
std::swap(result[i], result[rev[i]]);
}

for (size_t h = 2; h <= n; h <<= 1) {

ValueT wn, w;
if constexpr (is_modint_v<ValueT>) {
wn = qpow(ValueT(find_primitive_root<get_modint_mod_v<ValueT>>()),
(get_modint_mod_v<ValueT> - 1) / h);
} else if constexpr (std::is_same_v<ValueT, std::complex<double>>) {
wn = { cos(2*PI/h), sin(2*PI/h) };
} else {
[]<bool flag = false>(){
static_assert(flag, "FATAL ERR: FFT only support std::complex<double> and ModInt.");
}();
}

if (dir == TransformDirection::IDFT)
wn = ValueT(1) / wn;

for (size_t j = 0; j < n; j += h) {
w = 1;
for (size_t k = j; k < j + (h >> 1); k++, w *= wn) {
ValueT x = result[k], y = result[k + (h >> 1)] * w;
result[k] = x + y, result[k + (h >> 1)] = x - y;
}
}
}

if (dir == TransformDirection::IDFT) {
for (size_t i = 0; i < n; i++)
result[i] /= n;
}
}
};

}

/// ======================
/// Use the template above
/// ======================

const int MOD = 1004535809; // alternative: 1e9+7 leads to runtime error
using num_t = std::complex<double>;// alternative: zmile::ModInt<int, MOD>;
using dir_t = zmile::FFT<num_t>::TransformDirection;

int main() {
size_t n, m;
num_t val;
std::cin >> n >> m;

zmile::FFT<num_t> transformer{ n + m + 1 };
std::vector<num_t> poly1, poly2;

for (int i = 0; i <= n; i++) {
std::cin >> val;
poly1.push_back(val);
}
for (int i = 0; i <= m; i++) {
std::cin >> val;
poly2.push_back(val);
}

transformer.transform(poly1, poly1, dir_t::DFT);
transformer.transform(poly2, poly2, dir_t::DFT);

for (int i = 0; i < poly1.size(); i++) {
poly1[i] *= poly2[i];
}

transformer.transform(poly1, poly1, dir_t::IDFT);
for (int i = 0; i <= n + m; i++) {
std::cout << int(poly1[i].real() + 0.5) << ' '; // ModInt: directly output poly1[i]
}

return 0;
}

评论和共享

寒假训练题,比赛全名 XVIII Open Cup named after E.V. Pankratiev. Eastern Grand Prix。

Description

在三维整点空间 \(E\) 中,每个整点存了个数字,一开始数字都是 \(0\),每次对这样一个区域 \(S(x,y,z,a)\) 进行两种操作

  • \(M\) 操作 所有整点上的数字 \(+1\)
  • \(Q\) 操作 求所有整点上的数字和

\(M\) 操作全部做完后才会有 \(Q\) 操作。

\[ E:=\{(x,y,z)|1\le z\le y\le x\le n\}, \]

\[ S(x,y,z,a):=\{(x+u,y+v,z+w)|0\le w\le v\le u< a\}. \]

\[ n\le 100,\quad |M|\le 10^5,\quad |Q|\le 10^5. \]

阅读全文

WEEK201205

AGC010C

先找个非叶子作为根,(把 \(n=2\) 判掉),然后考虑一个等效次数 \(f(u)\),就是相当于一个节点和儿子必须满足方程:\(\exists\,x:f(u)=a[u]-x=sum-2x\) ,其中 \(x\) 是对当前节点的等效情形的操作次数。这样对于每个经过 \(u\) 的路径就可以合理地分配给各个儿子,从而分配到最后的叶子。于是 dfs 一遍判每个节点的解 \(x\) 是否存在就做完了。

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
// 静かな海
#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 = 1e5+3;
#define int long long

int n, a[N], f[N], d[N];
vector<int> G[N];

void dfs(int u, int fa) {
if (d[u] == 1) return void(f[u] = a[u]);

int sum = 0, mx = 0;
for (int v:G[u]) if (v^fa) {
dfs(v, u);
sum += f[v], mx = max(mx, f[v]);
}

f[u] = 2*a[u] - sum;
if (a[u] > sum || a[u] < mx || f[u] < 0)
puts("NO"), exit(0);
}

signed main() {
n = rd();
for (int i=1; i<=n; i++) a[i] = rd();
if (n == 2) return 0 * puts(a[1] == a[2] ? "YES" : "NO");
for (int i=1; i<n; i++) {
int u = rd(), v = rd();
G[u].push_back(v), G[v].push_back(u);
d[u]++, d[v]++;
}

int rt;
for (int i=1; i<=n; i++)
if (d[i] > 1) { rt = i; break; }

dfs(rt, 0);

puts(f[rt] ? "NO" : "YES");
}

AGC011D

有点水,推一推或者直接打表都可以发现每次要么第一个数取反要么整体左移并取反, 以至于很快尾部出现 BABA 型循环节,最后把所有数字顶掉,形成 1~2 周期的循环, 于是 bitset 暴力模拟一下即可。

不知道为啥 47 个点就是过不去,WA,就放这儿吧,反正只有我自己看这文章,懒得仔细看了……

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
// 静かな海
#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 = 1e5+3;

int n, k;
bitset<200000> b;

signed main() {
n = rd(), k = rd();
for (int i=0; i<n; i++)
b[i] = getchar() == 'B';

int tg = 0;
for (int i=1; i<=k && i<=2*n+1; i++) {
if (b[0] ^ tg) b>>=1, tg ^= 1, b[n-1] = tg;
else b[0].flip();
}

if (2*n+1 < k) {
int rem = k - 2*n - 1;
if (!(b[0] ^ tg)) tg ^= rem & 1;
}

for (int i=0; i<n; i++)
putchar((b[i]^tg) ? 'B' : 'A');

putchar('\n');
}

Over

一个国家有 \(N\) 个村庄,第 \(i\) 个村庄有一个奇妙的权值 \(A_i\),以及另一个奇妙的权值 \(B_i\)。 其中 \(B_i=\sum_j^i A_j\)。 我们保证 \(B_N=0\)

现在要从任意一个村庄出发,遍历除起点外任意不少于\(1\)个村庄,之后回到起始村庄。当从第\(i\)个村庄走到第\(j\)个村庄的时候,贡献是\(\dfrac{(A_i−A_j)B_iB_j}{2A_iA_j}\)

假设遍历顺序是 \(P_1,P_2,P_3,...,P_k,P_{k+1}\)(当然,由于起始位置必须相同,这里 \(P_{k+1}=P_1\)),他希望存在一个 \(2\le i\le k\),使得对于任意 \(j<i\), 都满足 \(B_{P_j}\le B_{P_{j+1}}\);而对于任意 \(k\ge j\ge i\), 都满足\(B_{P_j}\ge B_{P_{j+1}}\)

换句话说,\(B\) 权值在到达某个村庄之前是单调不降的,而之后又是单调不增的。在这个限制下最大化贡献和。


\[ \frac{(A_i−A_j)B_iB_j}{2A_iA_j}=\frac12\left(B_i\frac{B_j}{A_j}-B_j\frac{B_i}{A_i}\right) \]

于是求凸包面积即可

1
// gugu

评论和共享

WEEK201129

HDU6438 Buy and Resell

这个题目挺有意思的,值得记录下来。和以前一道CF一样。它们都是考虑一种“不关心具体方案”时的修改,即利用式子来进行“反悔”。

HDU6439 Congruence equation

记对参数 \(m\),这样的数列 \(\{C_k\}\) 的个数为 \(f(m)\)

  • 长度为 \(k\)
  • 对某些位置限制了必须为某值,而其它位置可以在有限域 \(F_m\) 中任选
  • \(\sum_{1\le i\le k}C_ix_i\equiv1\pmod m\),其中 \(x_i\) 是自由变量,这个方程要有整数解

你要计算 \(\sum_{m=1}^nf(m)\)

\(T\le100,k\le50,n\le10^9\),但最多对\(10\)组数据有 \(n\ge10^6\)


首先入手点当然是那个不定方程了,同余不用怕,多加一个系数为 \(m\) 的变量之后就变成普通不定方程了。

所以有解等价于 \(\gcd(C,m)=1\)\(C\) 是数列中所有数字的简记法。

但是还有一些位置已经定了值,我们不妨把它们先拉出来,把它们的 \(\gcd\) 设为 \(q\)。并且令 \(k\to\text{the number of free var }c_i\)

其实想到到这里应该就知道自己做完了这个不难的题目了,然而我却sb了,看到 \(\gcd=1\) 还想不到反演……

下面记枚举所有数列中不定的位置求和为 \(\sum_{C}\),实际上是 \(k\) 个求和号,那么答案就是

\[ \begin{aligned} \sum_{1\le m\le n}\sum_{C}[(C,q,m)=1] &=\sum_{1\le m\le n}\sum_{C}\sum_{d|(C,q,m)}\mu(d)\\ &=\sum_{d\le n}\mu(d)\sum_{m\le n}\sum_C[d|(C,q,m)]\\ &=\sum_{d\le n}\mu(d)[d|q]\sum_{m\le n}\left(\prod_{1\le h\le k}\sum_{1\le c_h\le m}[d|c_h]\right)\\ &=\sum_{d|q}\mu(d)\sum_{p\le \left\lfloor\large\frac nd\right\rfloor}p^k\\ \end{aligned} \]

这个式子好办,直接枚举因数,然后对于后面那个自然数幂和,暴力\(\mathcal O(k^2)\)预处理伯努利数即可。由于 \(q\le n\le 10^9\)\(\mathcal O(k^2+k\sqrt q)\) 是可以通过的。

当然,此外还有一种情形更棘手些,对于 \(q=0\) ,也就是没有限制,\(d|0\) 是(要视为)恒成立的,也就是 \(d\)\(1\to n\) 枚举。这个时候我们利用和杜教筛类似的交换和号方法可以直接得到

\[ =\sum_{1\le p\le n}p^k\sum_{dp\le n}\mu(d) \]

后面那个是 \(M\left(\left\lfloor\frac nd\right\rfloor\right)\),可以杜教筛,因为显然杜教筛 \(M(n)\) 时其实就会求出所有的 \(M\left(\left\lfloor\frac nd\right\rfloor\right)\)

口胡一下复杂度 \(\mathcal O(k^2+k\sqrt n+n^{2/3})\)

HDU6440 Dream

这个构造还是有点新奇的,幸好 fz 事构造大师hhh,于是我们的方案是这样的

\[ \forall x,y:x+y=1,x\times y=\min(x,y)+1 \]

其中本来是先想出了乘法,这样对幂就有

\[ a\ne0:a^0=1,\;a^1=1\times a=2,\;a^2=3,\;\cdots,\;a^{a-1}=a,\;a^a=a\cdots \]

HDU6442 GuGu Convolution

\(F(x)=\mathrm{EGF}\langle A^0,A^1,A^2,\cdots\rangle(x),G(x)=\mathrm{EGF}\left\langle 0,\left(\sqrt B\right)^1,0,\left(\sqrt B\right)^3,0,\left(\sqrt B\right)^5,\cdots\right\rangle(x)\),求 \(n![x^n](F\times G)(x)\)


比较水,但是很坑。根据 EGF 卷积,答案就是

\[ \sum_{k\text{ is odd}\atop 0\le k\le n}\binom nkA^{n-k}\left(\sqrt B\right)^{k}=\frac12[(A+\sqrt B)^n-(A-\sqrt B)^n] \]

然后显然可以快速幂,有两个坑点

  • 写矩阵快速幂常数太大容易 T,原因是有很多冗余运算,对 \(0\) 运算的那种。可以改成直接做线性变换,省去矩阵操作。
  • 模数任意,但是只要求 \(2\) 的逆元,写个欧拉定理很不值;有个 trick:可以全程 \(\pmod{2p}\) 然后最后换回去的答案是 \(\left\lfloor\dfrac{\rm ans}{2}\right\rfloor\)

评论和共享

WEEK201121

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\) 筛或洲阁筛解决。

评论和共享

拟阵通识

课件

学校好题交流时瞎写的,尽量照顾了线代水平不算高的选手,读起来难度应该不大。

拟阵交也就这一类套路题,还想练练可以做 Rainbow Graph 这题,比赛带上板子就好了。

顺便把课件末尾的几篇资料也读了x

评论和共享

Description

今年多校第一场的题哦

传送门

Analysis

看到积分非常傻眼,而且题目里还声称“答案是有理数”,这自然引起我们的好奇。注意到分子分母其实是齐次的,所以多半是什么东西消掉了才这样的吧x

上下都是 \(4N,2N\) ,不妨只考虑一个 \(N\),然后菜鸡的分析只会大暴力,最暴力的想法就是,呃,先换元试试看。\(x=\frac{1}{\tau}\) 代换后

阅读全文

Description

\(n,q\le 3\times10^5\),要你对 \(q\) 组询问 \((a,b,c,d)\) 回答

\[ \frac{d}{c+e^{ax+b}} \]

\(x_0=-b/a\) 处的泰勒展开 \((x-x_0)^n\) 项系数。

Analysis

作代换 \(t=ax+b\),不难发现答案就是 \([t^n]a^n\cdot\frac{d}{c+e^t}\) ,那么 \(a,b,d\) 都处理完了。

考虑求 \([x^n]\frac{1}{c+e^x}\)

Method 1

这是我的方法,比较直来直去,但也用到了不少有意思的东西。

阅读全文

离散技巧略点

(orz这是以前幼稚时期文章的搬运,后续部分一字未改,主要面向刚入门的初高中生读者以及希望自己写的过程能更加简洁的巨佬,有空再新加几个原则,希望有一天良好的规范和技巧能蔚然成风。

阅读全文
  • 第 1 页 共 1 页
作者的图片

7mile

八轨宇宙的七里征途


学生


E-Rev