CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » alchemist » weekly_digest_1
2020-2021:teams:alchemist:weekly_digest_1

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:alchemist:weekly_digest_1 [2020/05/09 12:47]
hardict [统计数列中上升子序列个数] 		2020-2021:teams:alchemist:weekly_digest_1 [2020/05/12 01:11] (当前版本)
mountvoom [肖思炀 MountVoom]
行 21: 行 21:
 模板题：https:​%%//​%%ac.nowcoder.com/​acm/​contest/​5157/​D 模板题：https:​%%//​%%ac.nowcoder.com/​acm/​contest/​5157/​D
  
-很容易从题目的形式看出来实际上就是对四个数列求三重卷积，第一重是$i|j$的子集卷积，第二重$(i|j)+k$的FFT/​NTT，第三重是$((i|j)+k)\otimes h$的FWT的异或卷积。代码如下：+很容易从题目的形式看出来实际上就是对四个数列求三重卷积，第一重是$i|j$的子集卷积，第二重$(i|j)+k$的FFT/​NTT，第三重是$((i|j)+k)\otimes h$的FWT的异或卷积。代码参考个人主页的子集卷积内容。
  
-<code cpp> +===== 龙鹏宇 Hardict =====
-#include <​bits/​stdc++.h>​+
  
-#define N 262144+==== 总结 ====
  
-using namespace std; +  ​- 多组数据多组询问尽可能考虑预处理,在单个数容斥中一般$\mu(i) \neq 0$才有贡献,可以预处理进行优化 
- +  - 计算几何处理相同点可以$\pm epsilon$
-const int mod = 998244353, inv2 = 499122177;​ +
- +
-int n; +
-int rev[N], lim, hib; +
-int A[N], B[N], C[N], D[N], popc[N]; +
-int f[20][N], g[20][N], h[20][N]; +
- +
-inline int Add(int u, int v) { return (u += v) >= mod ? u - mod : u; } +
- +
-inline void Inc(int &u, int v) { if ((u += v) >= mod) u -= mod; } +
- +
-inline int fpm(int x, int y) { +
-    int r = 1; +
-    while (y) { +
-        if (y & 1) r = 1LL * x * r % mod; +
-        x = 1LL * x * x % mod, y >>= 1; +
-    } +
-    return r; +
-} +
- +
-inline int read() { +
-    int x = 0; +
-    char ch = getchar();​ +
-    while (!isdigit(ch)) ch = getchar();​ +
-    while (isdigit(ch)) x = x * 10 + ch - '​0',​ ch = getchar();​ +
-    return x; +
-} +
- +
-void getrev(int len) { +
-    lim = 1, hib = -1; +
-    while (lim < len) lim <<= 1, ++hib; +
-    for (int i = 0; i < lim; ++i) +
-        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << hib); +
-} +
- +
-void fwtOr(int *a, bool type) { +
-    for (int mid = 1; mid < lim; mid <<= 1) +
-        for (int i = 0; i < lim; i += (mid << 1)) +
-            for (int j = 0; j < mid; ++j) +
-                if (type) Inc(a[i + mid + j], a[i + j]); +
-                else Inc(a[i + mid + j], mod - a[i + j]); +
-} +
- +
-void fwtXor(int *a, bool type) { +
-    static int x, y; +
-    for (int mid = 1; mid < n; mid <<= 1) +
-        for (int len = mid << 1, i = 0; i < n; i += len) +
-            for (int j = 0; j < mid; ++j) { +
-                x = a[i + j], y = a[i + mid + j]; +
-                a[i + j] = Add(x, y), a[i + mid + j] = Add(x, mod - y); +
-                if (!type) +
-                    a[i + j] = 1LL * inv2 * a[i + j] % mod, +
-                            a[i + mid + j] = 1LL * inv2 * a[i + mid + j] % mod; +
-            } +
-} +
- +
-void NTT(int *a, bool type) { +
-    for (int i = 0; i < lim; ++i) +
-        if (i < rev[i]) +
-            swap(a[i], a[rev[i]]);​ +
-    static int x, y; +
-    for (int mid = 1; mid < lim; mid <<= 1) { +
-        int len = mid << 1, wn = fpm(3, (mod - 1) / len); +
-        for (int i = 0; i < lim; i += len) +
-            for (int j = 0, w = 1; j < mid; ++j, w = 1LL * w * wn % mod) { +
-                x = a[i + j], y = 1LL * w * a[i + mid + j] % mod; +
-                a[i + j] = Add(x, y), a[i + mid + j] = Add(x, mod - y); +
-            } +
-    } +
-    if (!type) { +
-        reverse(a + 1, a + lim); +
-        int inv = fpm(lim, mod - 2); +
-        for (int i = 0; i < lim; ++i) +
-            a[i] = 1LL * inv * a[i] % mod; +
-    } +
-} +
- +
-int main() { +
-    n = read(), ++n; +
-    getrev(n + n - 1); +
-    for (int i = 0; i < lim; ++i) popc[i] = popc[i >> 1] + (i & 1); +
-    for (int i = 0; i < n; ++i) A[i] = read(), f[popc[i]][i] = A[i]; +
-    for (int i = 0; i < n; ++i) B[i] = read(), g[popc[i]][i] = B[i]; +
-    for (int i = 0; i < n; ++i) C[i] = read(); +
-    for (int i = 0; i < n; ++i) D[i] = read(); +
- +
-    for (int i = 0; i <= 17; ++i) +
-        fwtOr(f[i], true), fwtOr(g[i], true); +
-    for (int sa = 0; sa <= 17; ++sa) +
-        for (int sb = 0; sb + sa <= 17; ++sb) +
-            for (int i = 0; i < lim; ++i) +
-                h[sa + sb][i] = (h[sa + sb][i] + 1LL * f[sa][i] * g[sb][i]) % mod; +
-    for (int i = 0; i <= 17; ++i) +
-        fwtOr(h[i], false); +
-    for (int i = 0; i < lim; ++i) +
-        A[i] = h[popc[i]][i];​ +
- +
-    NTT(A, true), NTT(C, true); +
-    for (int i = 0; i < lim; ++i) +
-        A[i] = 1LL * A[i] * C[i] % mod; +
-    NTT(A, false); +
- +
-    fwtXor(A, true), fwtXor(D, true); +
-    for (int i = 0; i < lim; ++i) +
-        A[i] = 1LL * A[i] * D[i] % mod; +
-    fwtXor(A, false); +
- +
-    int Q = read(); +
-    while (Q--) printf("​%d\n", A[read()]);​ +
-    return 0; +
-} +
-</​code>​ +
- +
-===== 龙鹏宇 Hardict =====+
 ==== 统计数列中上升子序列个数==== ==== 统计数列中上升子序列个数====
  
行 152: 行 37:
 可以利用数组数组解决,​可是一般数列中会出现相同数,​需要预先离散化 可以利用数组数组解决,​可是一般数列中会出现相同数,​需要预先离散化
  
-这里有一个技巧,​假设数列长度为$n$,​可以令$b[i]=(n+1)*a[i]+n-i排序后利用b[]离散化即可得到严格上升下对应的rank\\若令b[i]=(n+1)*a[i]+i则可得到不严格上升的rank$+这里有一个技巧,​假设数列长度为$n$,​可以令$b[i]=(n+1)*a[i]+n-i$排序后利用$b[]$离散化即可得到严格上升下对应的$rank$ 
 + 
 +若令$b[i]=(n+1)*a[i]+i$则可得到不严格上升的$rank$
  
 === 例题 === === 例题 ===
行 163: 行 50:
 **题解:** **题解:**
  
-考虑$满足新数列\{p\}=\{a_{i} : d |b_{i}\}$,​求解$\{p\}$的上升子序列个数$cnt_{d}$再乘上容斥系数$coef_{d}$+考虑满足新数列$\{p\}=\{a_{i} : d |b_{i}\}$,​求解$\{p\}$的上升子序列个数$cnt_{d}$再乘上容斥系数$coef_{d}$
  
 即可得到$ans=\sum_{d=1}^{maxb}cnt_{d}coef_{d},​maxb=\max\limits_{1 \leq i\leq n}\{b_{i}\}$ 即可得到$ans=\sum_{d=1}^{maxb}cnt_{d}coef_{d},​maxb=\max\limits_{1 \leq i\leq n}\{b_{i}\}$
行 175: 行 62:
 还要预处理$\{i : d |b_{i}\}$进行优化 还要预处理$\{i : d |b_{i}\}$进行优化
  
-[[hardict_code1|代码]]+[[2020-2021:​teams:​alchemist:​weekly_digest_1:​hardict_code1|代码]]
 ===== 肖思炀 MountVoom ===== ===== 肖思炀 MountVoom =====
 +
 +=== 个人总结 ===
 +
 +$NullPointerException$
  
 === 其他 === === 其他 ===
行 189: 行 80:
  
 === 霍尔定理 === === 霍尔定理 ===
-[[2020-2021:​teams:​alchemist:​mountvoom:​hallTheorem|霍尔定理]] ​(题目在补了在补了qwq)+[[2020-2021:​teams:​alchemist:​mountvoom:​hallTheorem|霍尔定理]]
  
2020-2021/teams/alchemist/weekly_digest_1.1588999624.txt.gz · 最后更改: 2020/05/09 12:47 由 hardict

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3