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/08 20:36]
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; +
- +
-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 ​=====+
  
 +  - 多组数据多组询问尽可能考虑预处理,​在单个数容斥中一般$\mu(i) \neq 0$才有贡献,​可以预处理进行优化
 +  - 计算几何处理相同点可以$\pm epsilon$
 ==== 统计数列中上升子序列个数==== ==== 统计数列中上升子序列个数====
  
行 153: 行 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$
  
 === 例题 === === 例题 ===
行 164: 行 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}\}$
行 176: 行 62:
 还要预处理$\{i : d |b_{i}\}$进行优化 还要预处理$\{i : d |b_{i}\}$进行优化
  
-<code cpp> +[[2020-2021:​teams:​alchemist:​weekly_digest_1:​hardict_code1|代码]] 
-#include <​algorithm>​ +===== 肖思炀 MountVoom =====
-#include <​cstdio>​ +
-#include <​cstring>​ +
-#include <​iostream>​ +
-#include <​vector>​ +
-using namespace std;+
  
-using LL = long long; +=== 个人总结 ===
-const int MOD = 1e9 + 7; +
-const int MAXN = 1e5 + 5; +
-// Euler sieve +
-int prime[MAXN * 10], cnt_prime;​ +
-bool noprime[MAXN * 10]; +
-int mu[MAXN * 10]; +
-vector<​int>​ nozero_mu;​ +
-void Euler_sieve(int n); +
-// main +
-int N, M, K; +
-int a[MAXN], b[MAXN], p[MAXN], coef[MAXN * 10]; +
-LL discret[MAXN];​ +
-vector<​int>​ fac[MAXN * 10], buck[MAXN * 10]; +
-int solve(int d);+
  
-int main() { +$NullPointerException$
-  // +
-  cin >> N; +
-  for (int i = 1; i <= N; i++) { +
-    cin >> a[i]; +
-    discret[i] = 1LL * (N + 1) * a[i] + N - i; +
-  } +
-  sort(discret + 1, discret + 1 + N); +
-  // K = unique(discret + 1, discret + 1 + N) - discret - 1; +
-  K = N; +
-  for (int i = 1; i <= N; i++) +
-    a[i] = lower_bound(discret + 1, discret + 1 + K, +
-                       1LL * (N + 1) * a[i] + N - i) - +
-           ​discret;​ +
-  // for (int i = 1; i <= N; i++) cout << a[i] << endl; +
- +
-  int maxb = 0; +
-  for (int i = 1; i <= N; i++) { +
-    cin >> b[i]; +
-    buck[b[i]].push_back(i);​ +
-    maxb = max(maxb, b[i]); +
-  } +
-  Euler_sieve(maxb + 5); +
-  for (int i = 1; i <= maxb; i++) { +
-    for (int k : nozero_mu) { +
-      int j = i * k; +
-      if (j > maxb) break; +
-      coef[j] = (1LL * coef[j] + mu[k] * i + MOD) % MOD; +
-    } +
-  } +
- +
-  for (int i = 1; i <= maxb; i++) { +
-    for (int j = i; j <= maxb; j += i) +
-      for (int id : buck[j]) fac[i].push_back(id);​ +
-    sort(fac[i].begin(),​ fac[i].end());​ +
-  } +
- +
-  int ans = 0; +
-  for (int i = 1; i <= maxb; i++) +
-    if (coef[i]) { +
-      int tmp = 1LL * coef[i] * solve(i) % MOD; +
-      // cout << solve(i) << endl; +
-      ans = (ans + tmp) % MOD; +
-    } +
-  cout << ans << endl; +
-  return 0; +
-} +
- +
-class FenwickTree { +
- ​private:​ +
-  int n; +
-  int a[MAXN]; +
-  inline int lowbit(int x) { return x & (-x); } +
- +
- ​public:​ +
-  void init(int n0); +
-  void add(int pos, int key); +
-  int query(int pos); +
-}; +
-FenwickTree FT; +
-int solve(int d) { +
-  M = 0; +
-  for (int id : fac[d]) { +
-    p[++M] = a[id]; +
-    discret[M] = p[M]; +
-  } +
-  sort(discret + 1, discret + 1 + M); +
-  for (int i = 1; i <= M; i++) +
-    p[i] = lower_bound(discret + 1, discret + 1 + M, p[i]) - discret; +
-  int cnt = 0; +
-  FT.init(M);​ +
-  for (int i = 1; i <= M; i++) { +
-    int tmp = FT.query(p[i]);​ +
-    cnt = (cnt + tmp + 1) % MOD; +
-    FT.add(p[i],​ tmp + 1); +
-  } +
-  return cnt; +
-} +
- +
-void FenwickTree::​init(int n0) { +
-  n = n0; +
-  fill(a, a + n + 3, 0); +
-} +
- +
-void FenwickTree::​add(int pos, int key) { +
-  while (pos <= this->n) { +
-    this->​a[pos] = (this->​a[pos] + key) % MOD; +
-    pos += lowbit(pos);​ +
-  } +
-} +
- +
-int FenwickTree::​query(int pos) { +
-  int res = 0; +
-  while (pos) { +
-    res = (res + this->​a[pos]) % MOD; +
-    pos -= lowbit(pos);​ +
-  } +
-  return res; +
-} +
- +
-void Euler_sieve(int n) { +
-  mu[1] = 1; +
-  for (int i = 2; i <= n; i++) { +
-    if (!noprime[i]) { +
-      prime[++cnt_prime] = i; +
-      mu[i] = -1; +
-    } +
-    for (int j = 1; j <= cnt_prime && i * prime[j] <= n; j++) { +
-      noprime[i * prime[j]] = true; +
-      if (i % prime[j] == 0) break; +
-      mu[i * prime[j]] = -mu[i]; +
-    } +
-  } +
-  for (int i = 1; i <= n; i++) +
-    if (mu[i]) nozero_mu.push_back(i);​ +
-} +
-</​code>​ +
-===== 肖思炀 MountVoom =====+
  
 === 其他 === === 其他 ===
行 330: 行 80:
  
 === 霍尔定理 === === 霍尔定理 ===
-[[2020-2021:​teams:​alchemist:​mountvoom:​hallTheorem|霍尔定理]] ​(题目在补了在补了qwq)+[[2020-2021:​teams:​alchemist:​mountvoom:​hallTheorem|霍尔定理]]
  
2020-2021/teams/alchemist/weekly_digest_1.1588941361.txt.gz · 最后更改: 2020/05/08 20:36 由 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