[2018 Multi-University Training Contest 10] C. Calculate

Link: http://acm.hdu.edu.cn/showproblem.php?pid=6428

Statement:

Given \(1 \leq A, B, C \leq 10^7\), compute

\[ \sum_{i=1}^A \sum_{j=1}^B \sum_{k=1}^C \phi(\gcd(i, j^2, k^3)) \]

no more than 10 test cases.

Solution:

Consider the number of triples (i, j, k) such that \( \gcd(i, j^2, k^3) = d\), denoted as \(f(d)\). By Mobius inversion,

\[ f(d) = \sum_{i} \mu(i) g(di) \]

where \(g(d)\) is the number of triples satisfying \( d | \gcd(i, j^2, k^3) \), and the answer should be

\[ \sum_{d=1}^A f(d) \phi(d) \]

Now we try to compute \(g(d)\):

\[ g(d) = \sum_{i = 1}^A [d | i] \sum_{j = 1}^B [d | j^2] \sum_{k = 1}^C [d | k^3] \]

Let \(d = \prod {p_i}^{a_i} \) denote the unique factorization of d. Note that \(d | k^n \) whenever \( \prod {p_i}^{\lceil a_i / n \rceil} | k \).

Let \( h_n(d) = \prod {p_i}^{\lceil a_i / n \rceil} \), which denotes the minimum positive integer whose nth power is divisible by d. Now \(g(d)\) could be rewritten as

\[ g(d) = \lfloor \frac{A}{d} \rfloor \lfloor \frac{B}{h_2(d)} \rfloor \lfloor \frac{C}{h_3(d)} \rfloor \]

Plug in answer:

\[ \sum_{d=1}^A f(d) \phi(d) = \sum_{d=1}^A \phi(d) \sum_{i} \mu(i) g(di) = \sum_{q = 1}^A g(q) \sum_{ij = q} \mu(i) \phi(j) \]

where the Dirichlet convolution \( (\mu * \phi)(q) = \sum_{ij = q} \mu(i) \phi(j) \) is multiplicative and thus could be effectively precomputed (along with \(h_2\), \(h_3\)) by the sieve of Euler in linear time. Hence each test case could be done in \(O(A)\) time.

Source Code:

#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
    __func__, ##__VA_ARGS__)
#else 
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

namespace sieve {
  constexpr int MAXN = 10000007;
  bool p[MAXN];
  int prime[MAXN], sz;
  int pval[MAXN], pcnt[MAXN];
  unsigned h2[MAXN], h3[MAXN], phi[MAXN], muphi[MAXN];

  void exec(int N = 10000007) {
    p[0] = p[1] = 1;
    
    pval[1] = 1;
    pcnt[1] = 0;
    h2[1] = h3[1] = phi[1] = muphi[1] = 1;

    for (int i = 2; i < N; i++) {
      if (!p[i]) {
        prime[sz++] = i;
        for (LL j = i; j < N; j *= i) {
          int b = j / i;
          pval[j] = i * pval[b];
          pcnt[j] = pcnt[b] + 1;
          h2[j] = h2[b] * (pcnt[j] % 2 == 1 ? i : 1);
          h3[j] = h3[b] * (pcnt[j] % 3 == 1 ? i : 1);
          phi[j] = (i == j ? i-1 : phi[b] * i);
          muphi[j] = phi[j] - phi[b];
        }
      }
      for (int j = 0; i * prime[j] < N; j++) {
        int x = i * prime[j]; p[x] = 1;
        if (i % prime[j] == 0) {
          pval[x] = pval[i] * prime[j];
          pcnt[x] = pcnt[i] + 1;
        } else {
          pval[x] = prime[j];
          pcnt[x] = 1;
        }
        if (x != pval[x]) {
          int b = x / pval[x];
          h2[x] = h2[b] * h2[pval[x]];
          h3[x] = h3[b] * h3[pval[x]];
          muphi[x] = muphi[b] * muphi[pval[x]];
        }
        if (i % prime[j] == 0) break;
      }
    }
  }
}

int main() {
  using namespace sieve;
  exec();
  int T; scanf("%d", &T);
  while (T--) {
    unsigned a, b, c; scanf("%d%d%d", &a, &b, &c);
    unsigned res = 0;
    for (unsigned i = 1; i <= a; i++) 
      res += muphi[i] * (a / i) * (b / h2[i]) * (c / h3[i]); 
    printf("%d\n", res & 0x3fffffff);
  }
  return 0;
}

 

[2017 ACM-ICPC WF] Airport Construction

题意:

给定一个简单多边形(不一定凸),求完全位于该简单多边形边界及内部的最长线段的长度。点数200,坐标为整数且绝对值不超过1e6。

题解:

可以证明存在一条最优的的线段经过多边形的两个顶点。假设最优线段不经过顶点,则总可以向某一方向平移最优线段使得其长度不减少,直到碰到某一个顶点。然后绕着该顶点旋转,总有一个旋转方向使得线段的长度不会减小,直到线段碰到另一个顶点为止。

然后算法就很显然了:枚举多边形的两个顶点并将其延长,并用多边形将直线打散成若干条线段,删去在多边形外的线段,并将多边形内的连续线段合并,取最大的即可。枚举多边形两个顶点是\(O(n^2)\)的,打散成线段是\(O(n)\)的,判断线段是否在多边形内可以取中点,转化为点是否在多边形内,复杂度为\(O(n)\)。总复杂度为\(O(n^4)\),写的时候代码过于粗糙T了一发 QAQ

本题复杂度可以降到\(O(n^3)\),但具体做法还没仔细研究…

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i <=(n); i++)
#define range(x) begin(x), end(x)

typedef complex<double> pt, vec;
typedef pair<pt, pt> seg;

const double EPS = 1e-8;
int fcmp(double a, double b = 0.0) {
  if (fabs(a - b) < EPS) return 0;
  return a < b ? -1 : 1;
}

double operator * (pt a, pt b) {
  return a.real() * b.imag() - a.imag() * b.real();
}

double operator , (pt a, pt b) {
  return a.real() * b.real() + a.imag() * b.imag();
}

inline bool ptOnSeg(pt p, seg s){
    vec v1 = s.first - p, v2 = s.second - p;
    return fcmp((v1, v2)) <= 0 && fcmp(v1 * v2) == 0;
}

inline pt getIntersection(pt P, vec v, pt Q, vec w) {
    return P + v * (w*(P-Q)/(v*w));
}

// -1 outside the polygon
// 0  on the border of the polygon
// 1  inside the polygon
int ptOnPoly(pt p, pt* poly, int n){
//  fprintf(stderr, "(%.7f, %.7f)\n", p);
    int wn = 0;
    for (int i = 0; i < n; i++){
        if (ptOnSeg(p, {poly[i], poly[i+1]})) return 0;
        int d1 = fcmp(poly[i].imag() - p.imag()), 
            d2 = fcmp(poly[i+1].imag() - p.imag()),
            k = fcmp((poly[i+1] - poly[i])*(p - poly[i]));
        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    return wn ? 1 : -1;
}

istream& operator >> (istream& lhs, pt& rhs){
  double x, y;
  lhs >> x >> y;
  rhs = {x, y};
  return lhs;
}

int n;
vector<pt> poly;
double ans = 0.0;

void attempt(pt a, pt b) {
  vector<pt> points;
  rep (i, n) 
    if (fcmp((b-a)*(poly[i]-a)) * fcmp((b-a)*(poly[i+1]-a)) <= 0) {
      auto vec1 = b-a, vec2 = poly[i+1] - poly[i];
      if (fcmp(vec1 * vec2) == 0) {
        points.push_back(poly[i]);
        points.push_back(poly[i+1]);
      } else {
        points.push_back(getIntersection(a, b-a, poly[i], poly[i+1]-poly[i]));
      }
    }
  sort(range(points), [] (pt a, pt b) {
        return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
      });
  points.resize(unique(range(points), [] (pt a, pt b) {
          return fcmp(a.real(), b.real()) == 0 && fcmp(a.imag(), b.imag()) == 0;
        }) - points.begin());
  double cur = 0.0;
  assert(points.size() > 1);
  for (int i = 1; i < points.size(); i++) {
    if (ptOnPoly((points[i]+points[i-1]) / 2.0, poly.data(), n) >= 0) {
      cur += abs(points[i] - points[i-1]);
    } else {
      cur = 0.0;
      if (abs(points.back() - points[i]) <= ans) return;
    }
    ans = max(ans, cur);
  }
}

int main() {
  cin >> n; poly.resize(n);
  rep (i, n) cin >> poly[i];
  poly.push_back(poly[0]);
  rep (i, n) {
    rep (j, i) {
      attempt(poly[i], poly[j]);
    }
  }
  printf("%.8f\n", ans);
  return 0;
}

2018牛客暑期ACM多校训练营(第一场)题解

A. Monotonic Matrix

给定\(1\leq m,n \leq 1000\),求满足下列条件的\(m \times n\)矩阵个数,使得

  • \(a_{i,j} \in \{0, 1, 2\}\)
  • 每一行从左到右和每一列从上到下单调不减

题解:考虑每一行大于等于1和大于等于2的位置,其实就是要求两个单调不减的数列\(\{a_i\}, \{b_i\}\)的个数,满足对于任意\(i\),有\(a_i \leq b_i\)。

B. Symmetric Matrix

给定\(1 \leq n \leq 10^5\),求满足每个元素为非负整数,主对角线全0,每一行和为2的\(n \times n\)的对称矩阵的数量。

题解:把矩阵想象成邻接矩阵,就是要求顶点带标号的所有不允许自环、但允许重边的2-正则图的数量。

C. Fluorescent 2

在模2域下,给定\(m \times n\)的01矩阵\(M\),\(1 \leq n \leq 50\),\(1 \leq m \leq 1000\),求对于每一个\(n\)维向量\(v\),\(Mv\)中0的个数的三次方的和。

D. Two Graphs

给定图\(G_1 = (V, E_1), G_2 = (V, E_2)\),求有多少\(E_1\)的子集\(E’\),使得\((V, E’)\)与\(G_2\)同构。点数不超过8。

题解:枚举所有的排列,如果构成子图,就把选出来的边用bitmap表示出来,最后去重即可。

E. Removal

给定\(1 \leq n \leq 10^5\)个数的序列,每个数为不超过\(k\)的正整数。问删掉\(m\)个数后,有多少种不同的子序列。\(k, m\)不超过10。

题解:用dp[i][j][k]表示前i个数删去j个数后,最后一个数为k的方案数。可以在\(O(1)\)时间内转移。

F. Sum of Maximum

给定数列\(a_1, a_2, \cdots, a_n\),求

\[\sum_{x_1=1}^{a_1} \sum_{x_2=1}^{a_1} \cdots \sum_{x_n=1}^{a_n} \max\{x_1, x_2, \cdots, x_n\}\]

题解:把\(\max\{x_1, x_2, \cdots, x_n\}\)写为\(\sum_{m=1}^a [\exists i, x_i \geq m]\),进而改写为\(\sum_{m=1}^a 1-[\forall i, x_i < m]\)。将\(a_i\)排序后,从大到小分段计算,每一段都是\(x_i\)的一个前缀积乘以\(i^k\)的求和,后者可用Lagrange插值法快速计算。

G. Steiner Tree

H. Longest Path

I. Substring

给一个字符集为{a,b,c}的字符串,求在同构意义下的子串的等价类的数目。两个串同构当且仅当长度相等,并且存在字符集到字符集的双射f,使得一个串经过f变换后变成另一个串。

题解:将原串经过6种双射f后变成的6个串丢到SAM里,求出所有本质不同的子串。含有大于等于2种子串有6中不同的同构串,而只含有1种字符的串只有3中不同的同构串,分类讨论一下即可。

J. Different Integers

给一个序列,每次询问给出一个区间,求序列扣除这个区间后,有多少个不同数。

题解:在某次询问中,某数不出现当且仅当这个数第一次出现到最后一次出现包含于询问区间中即可。只要离线排序一下,按右端点的顺序处理即可。

2017-2018 问题求解(四)上机考试题解

Day1

A 差异度

题意:给\(n (1 \leq n \leq 10^5)\)个20位的01串,求两两之间hamming距离的最小值。

解法:此题解法甚多。下面列举3个常见的解法:

  1. 注意到当\(n\)很大时,最终答案不会太大(考虑一个01串hamming距离为\(d\)的邻域大小随\(d\)是指数增长的,然后用鸽巢原理即可)。所以,从小到大枚举答案\(d\),并在每个串的\(d\)-邻域内搜索即可。
  2. 建图。将所有20位的01串视为顶点,相差1位的两个串连边。问题就变成了:给定一个顶点子集,求这个子集中两两距离的最小值。这用多线程bfs就可以解决。时间复杂度为\(2^{20}*20\)。
  3. 用FWT处理出所有可能的异或值,取popcount最小的那个即可。(FWT课内没学,用了感觉有点犯规,但写起来方便是真的

B 工作安排

题意:某人有\(T (0 \leq T \leq 100)\)时间,\(N (0 \leq N \leq 100)\)组工作。每组工作有3种类型:至多选一个做,至少选一个做,无限制。每组工作中最多有100个工作,每个工作有完成的时间和所能得到的收益值。求所能获得的最大收益。

题解:较为复杂的背包问题。用常规的dp就可以解决。对于每组工作的附加限制,在更新dp值的时候需要特殊处理。

Day2

A 矩阵分割游戏

题面:NOI1999 棋盘分割

题意:给一个8*8的矩阵,每次可以横着或竖着掰成两半并舍弃一块,最后得到\(n\)块子矩阵。求子矩阵数字和的标准差的最小值。

题解:由gay率论相关知识,要使标准差取得最小值,只要让平方和最小即可(因为和是固定的)。然后dp或者记忆化爆搜即可。

B 旅行箱

题意:有\(n \leq 42\)个数,取出它的一个子集,使得子集和在不超过\(W\)的前提下,使得子集和最大。(简单背包问题)

题解:用meet-in-the-middle思想。将集合分成两部分,预处理出每部分的所有子集和。然后将这些子集和排序,对于一部分的某个子集和\(S\),在另一部分中找出不超过\(W-S\)的最大子集和,然后取最大值即可。复杂度\(O(n2^{n/2})\)。

2018 ACM-ICPC China Jiangsu Provincial Programming Contest

A. 签到题

B. 滚动数组DP

C. ???

D. \( \frac{(\sum_{i=1}^n U[i])!}{\prod_{i=1}^n U[i]!} \)

E. Catalan数?

F. 预处理dfs序,按照F的值的顺序更新树状数组求方案数

G. 每M个数分为一组,组内求出所有前缀积和后缀积。每个window就可以拆成一个前缀积和一个后缀积的乘积。

H. Berlekamp-Massey模板题

I. 将矩阵乘法的定义中,乘法改为加法,加法改为max,然后求个矩乘快速幂

J. 高精度

K. 求出最短路图中除起点外所有点的入度之积