Primes

题目描述

This is an interactive problem.
For two positive integers $x, y$, we define $\pi(x, y)$ to be the number of distinct primes that divide both $x$ and $y$. For example $\pi(2, 3) = 0, \; \pi(8, 16) = 1$ and $\pi(30, 105) = 2$.
For two positive integers $a, b$, where $a \le b$, we define $S(a, b)$ to be the sum of values $\pi(x, y)$ over all pairs of integers $(x, y)$ satisfying $a \le x \lt y \le b$.
Your task is to compute the values $S(a, b)$ for many query pairs $(a, b)$. To make your task more challenging, all the queries have to be answered online.

题意概述

给定两个整数$a, b$,定义$\pi(x, y)$为所有整除$x$和$y$的质数的个数,$S(a, b)$为所有满足$a \le x \lt y \le b$的$\pi(x, y)$的和,求$S(a, b)$。有$q$组询问,强制在线。

数据范围:$1 \le q \le 5 \times 10^4, \; 1 \le a \le b \le 10^6$。

算法分析

分别考虑每个质数对答案的贡献。若在区间$[a, b]$中有$k$个数能被质数$p$整除,则$p$对答案的贡献为${k \choose 2}$。

首先筛出所有质数。但是每次询问直接枚举质数会超时。考虑对于一个整数$n$,$\lfloor {n \over i} \rfloor$只有$O(\sqrt{n})$种不同的取值。因此可以对$\lfloor {a \over i} \rfloor$和$\lfloor {b \over i} \rfloor$进行分段枚举。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 1000005;

int tp, prime[N], rec[N], vis[N], sum[N];

void init() {
    for (int i = 2; i < N; ++i) {
        if (!vis[i]) {
            prime[tp++] = i;
        }
        for (int j = 0; j < tp && i * prime[j] < N; ++j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
    for (int i = 2; i < N; ++i)
        sum[i] = sum[i - 1] + !vis[i];
}

int main() {
    init();
    int q;
    scanf("%d", &q);
    for (; q--;) {
        int a, b;
        scanf("%d%d", &a, &b);
        long long ans = 0;
        for (int i = 0; i < tp && prime[i] < b;) {
            int cnt = b / prime[i] - (a - 1) / prime[i];
            int nxt = 1e9;
            if (b / prime[i]) nxt = std::min(nxt, b / (b / prime[i]));
            if ((a - 1) / prime[i]) nxt = std::min(nxt, (a - 1) / ((a - 1) / prime[i]));
            ans += 1ll * cnt * (cnt - 1) / 2 * (sum[nxt] - i);
            i = sum[nxt];
        }
        printf("%lld\n", ans);
        fflush(stdout);
    }
    return 0;
}

Black-White Balls

题目描述

$n$ black and white balls were put into a bag. Petya doesn’t know exactly how many black balls are there among them. He knows, however, that there are $0, 1, \ldots, n$ black balls among all balls in the bag with equal probability.
Petya took $l$ balls from the bag at random, and $l_1$ of them turned out black, while $l_2$ other turned out white ($l_1+l_2=l$). Now he wants to predict how many black balls were there initially in the bag. Of course, if $l \lt n$, he can’t be sure in his prediction, but he wants to predict a segment $[a, b]$, such that the amount $k$ of black balls belongs to it with probability at least $p$.
You are given $n, l_1, l_2$ and $p$, and you must find such $a$ and $b$ that $b-a$ is minimal possible. If there are several such pairs $(a, b)$, choose the one with the smallest $a$.

题意概述

袋子里有$n$个球,每个球可能是黑色或白色。已知黑球个数在$0, 1, \ldots, n$之间等概率分布。现在从中取出$l$个球,其中有$l_1$个黑球和$l_2$个白球($l_1+l_2=l$)。要求找到一个最短的区间$[a, b]$,使得黑球个数在$[a, b]$中的概率至少为${p \over 100}$。若有多个这样的区间,输出$a$最小的。
数据范围:$1 \le n \le 50, \; 0 \le l_1 \le n, \; 0 \le l_2 \le n-l_1, \; 0 \le p \le 100$。

算法分析

令事件$A$为取出的$l$个球中有$l_1$个黑球,事件$B_i$为袋子里有$i$个黑球。根据贝叶斯定理
$$P(B_i|A)={P(B_i)P(A|B_i) \over \sum_{j=0}^n P(B_j)P(A|B_j)}$$
而我们知道
$$P(B_i)={1 \over n+1}, \; P(A|B_i)={{i \choose l_1}{n-i \choose l_2} \over {n \choose l}}$$
因此可以计算出$P(B_i|A)$,接下来只要枚举区间即可。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 55;
double a[N];

double get_c(int n, int m) {
  if (n < m)
    return 0;
  double ret = 1;
  for (int i = 0; i < m; ++i)
    ret *= 1. * (n - i) / (m - i);
  return ret;
}

int main() {
  int n, l1, l2, p;
  scanf("%d%d%d%d", &n, &l1, &l2, &p);
  double b = 0;
  for (int i = 0; i <= n; ++i)
    b += a[i] = 1. / (n + 1) * get_c(i, l1) * get_c(n - i, l2) / get_c(n, l1 + l2);
  for (int i = 1; i <= n + 1; ++i)
    for (int j = 0; j + i - 1 <= n; ++j) {
      double sum = 0;
      for (int k = j; k <= j + i - 1; ++k)
        sum += a[k];
      if (sum / b * 100 + 1e-12 >= p)
        return printf("%d %d\n", j, j + i - 1), 0;
    }
  return 0;
}

Fermat’s Last Theorem

题目描述

Given a positive integer $n$ and a positive prime number $p$, find $x, y$ and $z$ such that $x^n+y^n \equiv z^n \pmod p$ and $x, y$ and $z$ are nonzero modulo $p$ or report that there’s no such triple.

题意概述

给定一个整数$n$和一个质数$p$,判断方程$x^n+y^n \equiv z^n \pmod p \; (1 \le x, y, z \lt p)$是否存在整数解,若存在则给出一组解。有$T$组数据。
数据范围:$1 \le T \le 1000, \; 3 \le n \le 10^6, \; 2 \le p \le 10^6$。

算法分析

为了方便,以下同余方程模数均为$p$。
求出$p$的原根$g$,设$x=g^{k_1}, \; y=g^{k_2}, \; z=g^{k_3}$,方程变为
$$g^{k_1n}+g^{k_2n} \equiv g^{k_3n}$$
令$G=g^n$,则
$$G^{k_1}+G^{k_2} \equiv G^{k_3}$$
由于$g$是原根,可知$G \not \equiv 0$,因此
$$
\begin{align}
G^{k_1-k_2}+1 &\equiv G^{k_3-k_2} \\
G^{k_1-k_3}+G^{k_2-k_3} &\equiv 1
\end{align}
$$
根据费马小定理,$G^{p-1} \equiv 1$,所以只要从$1$到$p-1$枚举$i$,判断是否存在$j \le i$满足
$$G^i+1 \equiv G^j \lor G^j+1 \equiv G^i \lor G^i+G^j \equiv 1$$
若存在,则找到了一组解。若枚举到$i$时发现存在$j \lt i$满足$G^i \equiv G^j$,说明开始循环,直接输出无解。根据抽屉原理,枚举的次数不会太多。
此题时限较小,不能每组询问都清空数组,可以使用时间戳。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 1000005;
int a[N], b[N], pri[N];

int power(int a, int b, int p) {
  int ret = 1;
  for (; b; b >>= 1)
    b & 1 && (ret = 1ll * ret * a % p), a = 1ll * a * a % p;
  return ret;
}

int get_prt(int p) {
  int top = 0, k = p - 1;
  for (int i = 2; i * i <= k; ++i)
    if (!(k % i)) {
      pri[top++] = i;
      for (; !(k % i); k /= i)
        ;
    }
  if (k > 1)
    pri[top++] = k;
  for (int i = 2; i <= p - 1; ++i) {
    bool fg = 1;
    for (int j = 0; fg && j < top; ++j)
      fg &= power(i, (p - 1) / pri[j], p) > 1;
    if (fg)
      return i;
  }
  return 0;
}

int main() {
  int T;
  scanf("%d", &T);
  for (int n, p; T--;) {
    scanf("%d%d", &n, &p);
    int g = get_prt(p), gn = power(g, n, p), x = 0, y = 0, z = 0;
    for (int i = 1, G = gn; i <= p - 1; ++i, G = 1ll * G * gn % p)
      if (b[G] == T + 1)
        break;
      else {
        a[G] = i, b[G] = T + 1;
        if (b[G + 1] == T + 1) {
          x = power(g, i, p), y = 1, z = power(g, a[G + 1], p);
          break;
        }
        if (b[G - 1] == T + 1) {
          x = power(g, a[G - 1], p), y = 1, z = power(g, i, p);
          break;
        }
        if (b[1 - G + p] == T + 1) {
          x = power(g, i, p), y = power(g, a[1 - G + p], p), z = 1;
          break;
        }
      }
    x ? printf("%d %d %d\n", x, y, z) : puts("-1");
  }
  return 0;
}

Divisibility

题目描述

Inspired by Stephen Graham, the King of Berland started to study algorithms on strings. He was working days and nights, having a feeling that the full potential in this area is still to be unlocked. And he was right!
One day, all the sudden, he made a huge breakthrough by discovering the fact that strings can be magically transformed into integer numbers. It was so simple! You just have to map different letters to different digits and be careful enough not to introduce any leading zeroes.
Here is what he wrote in his textbook about the string ‘lalala’:

  • it can be transformed to an $282828$ by mapping ‘l’ to $2$, and ‘a’ to $8$,
  • it can also be transformed to $909090$ by mapping ‘l’ to $9$, and ‘a’ to $0$,
  • acouple of examples of invalid transformations are $050505$ (the resulting number has a leading zero), $333333$ (different letters are mapped to the same digit), $123456$ (no mapping to the original letters at all).

But then things started to become more interesting. Obviously, it was known from very beginning that a single string can potentially be mapped to a variety of different integer numbers. But the King couldn’t even imagine that all numbers produced by the same string pattern might have common properties!
For example, every single number that can be produced from string ‘lalala’ is always divisible by $259$, irrespective of the letter-to-digit mapping you choose. Fascinating!
So the King ended up with the following problem. For any given string, he wanted to come up with an algorithm to calculate the set of its divisors. A number is called a divisor of the given string if all positive integers, that could possibly be produced from the given string, are divisible by it.
As usual, the King desperately wants you to help him, so stop thinking and start acting!

题意概述

给定一个字符集大小不超过$10$的字符串$s$。定义一个数字是合法的,当且仅当它没有前导零,位数等于$|s|$,且它从高到低的第$i$位和第$j$位相等当且仅当$s_i=s_j$。求出所有能整除每一个合法数字的数。有$n$组数据。
数据范围:$1 \le n \le 100, \; 1 \le |s| \le 14$。

算法分析

如果我们求出了所有合法数字的GCD,那么答案就是GCD的所有约数。
为了方便,我们设字符串的下标从$1$开始。
令$g$等于所有合法数字的GCD。首先考虑它的下界。假设字符$i$在字符串中出现的次数为$a_i$,出现的位置是$p_{i, 1}, p_{i, 2}, \ldots, p_{i, a_i}$。定义字符$i$的价值$v_i=\sum_{j=1}^{a_i} 10^{|s|-p_{i, j}}$。显然,所有合法的数字都可以被表示为$\sum k_iv_i$,其中$k_i$表示字符$i$变成的数字。所以,$g$的下界为$(v_a, v_b, \ldots, v_z)$。
考虑$g$的上界。分两种情况讨论。

  • 引理 $\forall a \le b, \; (a, b) \mid b-a$。

当字符集大小小于$10$时,对于每一个$i$,总能找到一个合法的数$x$使得$x+v_i$也合法。这是因为总有一个合法的数包含$k_i$但不包含$k_i+1$。根据引理,$(x, x+v_i) \mid v_i$。由于$x$和$x+v_i$均合法,因此$g \mid (x, x+v_i)$,即$g \mid v_i$。所以,$g$的上界为$(v_a, v_b, \ldots, v_z)$。结合下界,$g=(v_a, v_b, \ldots, v_z)$。
当字符集大小等于$10$时,要将某个$k_i$加一就必须将另一个$k_j$减一。如果对于不同的$i, j$,有$v_i, v_j \gt 0 \land v_i \lt v_j$,那么$g \mid v_j-v_i$。令$S=\{v_j-v_i \mid v_i, v_j \gt 0 \land v_i \lt v_j\}$。对于一个合法的数,它加上/减去$S$中的某些数后仍是一个合法的数;对于$S$中的数,存在一个合法的数加上/减去它之后仍是一个合法的数。即一个合法的数$x$与$S$中的数加减可以得到所有合法的数。令$h$等于$S$中所有数的GCD,那么显然,$g$的下界为$(x, h)$。又因为$g \mid x$且$g$整除$S$中的所有数,所以$g$的上界也是$(x, h)$。即$g=(x, h)$。
求$g$的所有约数可以先分解质因数再DFS。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const L = 15;
static int const M = 10000005;
char s[L];
int top, cnt, cc, p[M];
long long v[26], dv[L], dc[L], ans[M];

long long get_gcd(long long a, long long b) {
  for (long long c; b; c = a % b, a = b, b = c)
    ;
  return a;
}

void init() {
  top = 0;
  for (int i = 2; i < M; ++i) {
    if (!p[i])
      p[top++] = i;
    for (int j = 0; j < top; ++j) {
      int k = i * p[j];
      if (k >= M)
        break;
      p[k] = 1;
      if (!(i % p[j]))
        break;
    }
  }
}

void dfs(int t, long long v) {
  if (t == cnt)
    return void(ans[cc++] = v);
  for (int i = 0; i <= dc[t]; ++i, v *= dv[t])
    dfs(t + 1, v);
}

int main() {
  int n;
  scanf("%d", &n), init();
  for (int _ = 1; _ <= n; ++_) {
    printf("Case %d:", _), scanf("%s", s);
    int len = strlen(s), st = 0;
    for (int c = 0; c < 26; ++c) {
      v[c] = 0;
      for (int i = 0; i < len; ++i) {
        v[c] *= 10;
        if (s[i] == c + 'a')
          ++v[c];
      }
      st += v[c] > 0;
    }
    long long gcd = 0;
    if (st < 10)
      for (int i = 0; i < 26; ++i)
        gcd = get_gcd(gcd, v[i]);
    else {
      int k = 0;
      for (int i = 0; i < 26; ++i)
        if (v[i])
          gcd += k++ * v[i];
      for (int i = 0; i < 26; ++i)
        for (int j = 0; j < 26; ++j)
          if (v[i] && v[j] && v[i] < v[j])
            gcd = get_gcd(gcd, v[j] - v[i]);
    }
    cnt = cc = 0;
    for (int i = 0; i < top && 1ll * p[i] * p[i] <= gcd; ++i)
      if (!(gcd % p[i])) {
        dv[cnt] = p[i], dc[cnt] = 0;
        for (; !(gcd % p[i]);)
          gcd /= p[i], ++dc[cnt];
        ++cnt;
      }
    if (gcd > 1)
      dv[cnt] = gcd, dc[cnt] = 1, ++cnt;
    dfs(0, 1), std::sort(ans, ans + cc);
    for (int i = 0; i < cc; ++i)
      printf(" %lld", ans[i]);
    puts("");
  }
  return 0;
}

Gena vs Petya

题目描述

Gena and Petya love playing the following game with each other. There are $n$ piles of stones, the $i$-th pile contains $a_i$ stones. The players move in turns, Gena moves first. A player moves by choosing any non-empty pile and taking an arbitrary positive number of stones from it. If the move is impossible (that is, all piles are empty), then the game finishes and the current player is considered a loser.
Gena and Petya are the world famous experts in unusual games. We will assume that they play optimally.
Recently Petya started to notice that Gena wins too often. Petya decided that the problem is the unjust rules as Gena always gets to move first! To even their chances, Petya decided to cheat and take and hide some stones before the game begins. Since Petya does not want Gena to suspect anything, he will take the same number of stones $x$ from each pile. This number $x$ can be an arbitrary non-negative integer, strictly less that the minimum of $a_i$ values.
Your task is to find the number of distinct numbers $x$ such that Petya will win the game.

题意概述

给定$n$个正整数$a_i$,求有多少个非负整数$x$,满足$x$小于所有给定的数,且所有给定的数减去$x$之后的异或和为$0$。
数据范围:$1 \le n \le 2 \times 10^5, \; 1 \le a_i \le 10^{18}$。

算法分析

Nim游戏后手胜利的条件是所有数的异或和为$0$。
枚举$x$显然不可行。可以尝试从低位到高位依次确定。
考虑低位对高位的影响,易知只有当低位退位时才会改变高位。而对于每一位,若此位上有偶数个$0$,则此位可以填$1$,若有偶数个$1$则可以填$0$(这样才能使得异或和为$0$)。
令$f_{i, j}$表示从低到高处理到第$i$位时,有$j$个数字在第$(i+1)$位退位的方案数。根据退位的性质,这$j$个数字一定是所有给定的数按后$i$位从小到大排序后的前$j$个。可以在枚举$i$的同时基数排序,枚举$j$的同时维护第$i$位上$0$和$1$的个数(会受退位影响),若满足条件则转移(注意此位填$1$时还要考虑此位$0$的退位)。
最后需要特判一下$x$不能等于所有给定的数中最小的数。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 200005;
static int const M = 65;
int a[N], cnt[M], f[M][N], s[2][N];

signed main() {
  int n;
  scanf("%lld", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld", a + i);
    for (int j = 0; j < M; ++j)
      cnt[j] += a[i] >> j & 1;
  }
  f[0][0] = 1;
  for (int i = 0; i < M - 1; ++i) {
    int c0 = n - cnt[i], c1 = cnt[i], c = 0;
    for (int j = 0; j <= n; ++j) {
      if (j)
        if (a[j - 1] >> i & 1)
          ++c0, --c1;
        else
          --c0, ++c1, ++c;
      if (!(c0 & 1))
        f[i + 1][c + c0] += f[i][j];
      if (!(c1 & 1))
        f[i + 1][c] += f[i][j];
    }
    *s[0] = *s[1] = 0;
    for (int j = 0; j < n; ++j)
      s[a[j] >> i & 1][++*s[a[j] >> i & 1]] = a[j];
    for (int j = 1; j <= *s[0]; ++j)
      a[j - 1] = s[0][j];
    for (int j = 1; j <= *s[1]; ++j)
      a[*s[0] + j - 1] = s[1][j];
  }
  int sum = 0;
  for (int i = 1; i < n; ++i)
    sum ^= a[i] - a[0];
  printf("%lld\n", f[M - 1][0] - (sum == 0));
  return 0;
}

Kyoya and Train

题目描述

Kyoya Ootori wants to take the train to get to school. There are $n$ train stations and $m$ one-way train lines going between various stations. Kyoya is currently at train station $1$, and the school is at station $n$. To take a train, he must pay for a ticket, and the train also takes a certain amount of time. However, the trains are not perfect and take random amounts of time to arrive at their destination. If Kyoya arrives at school strictly after $t$ time units, he will have to pay a fine of $x$.
Each train line is described by a ticket price, and a probability distribution on the time the train takes. More formally, train line $i$ has ticket cost $c_i$, and a probability distribution $p_{i, k}$ which denotes the probability that this train will take $k$ time units for all $1 \le k \le t$. Amounts of time that each of the trains used by Kyouya takes are mutually independent random values (moreover, if Kyoya travels along the same train more than once, it is possible for the train to take different amounts of time and those amounts are also independent one from another).
Kyoya wants to get to school by spending the least amount of money in expectation (for the ticket price plus possible fine for being late). Of course, Kyoya has an optimal plan for how to get to school, and every time he arrives at a train station, he may recalculate his plan based on how much time he has remaining. What is the expected cost that Kyoya will pay to get to school if he moves optimally?

题意概述

有$n$座城市和$m$条铁路,第$i$条铁路从$a_i$号城市出发,到达$b_i$号城市,票价为$c_i$。某人要在$t$个单位时间内从$1$号城市到$n$号城市,如果超过时间就会被罚款$x$。已知每次搭乘第$i$条铁路有$p_{i, k}$的概率需要$k \; (1 \le k \le t)$个单位时间。求在采取最优策略的情况下总花费的期望。
数据范围:$2 \le n \le 50, \; 1 \le m \le 100, \; 1 \le t \le 20000, \; 0 \le x \le 10^6$。

算法分析

首先考虑最暴力的DP。令$f_{i, j}$表示当前时刻为$j$,在最优策略下从$i$号城市到$n$号城市的总花费的期望。那么
$$
f_{i, j}=
\begin{cases}
\min(c_e+\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k} \mid e \in [1, m] \land a_e=i), & i \lt n \land j \le t \\
d_{i, n}+x , & i \lt n \land j \gt t \\
0, & i=n \land j \le t \\
x, & i=n \land j \gt t
\end{cases}
$$
第二部分中的$d_{i, n}$表示在只考虑铁路票价的情况下从$i$号城市到$n$号城市的最小花费(因为已经超时了,所以不如走总票价最少的路)。
这样做的复杂度是$O(mt^2)$的,需要对它进行优化。令
$$S_{e, j}=\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k}$$
转移方程的第一部分变为
$$f_{i, j}=\min(c_e+S_{e, j} \mid e \in [1, m] \land a_e=i)$$
对于$S$,它类似于卷积,可以将其中一部分翻转后用FFT求值;对于$f$,可以用CDQ分治,统计较大的$j$对较小的$j$的贡献。
具体来说,假设我们要计算$l \le j \le r$的$f_{i, j}$,令$mid=\lfloor {l+r \over 2} \rfloor$,那么先计算$mid \lt j \le r$的$f_{i, j}$,用这些来更新$l \le j \le mid$的$S_{e, j}$($m$条边分别用FFT更新,复杂度$O(m(r-l)\log (r-l))$),最后计算$l \le j \le mid$的$f_{i, j}$。当$l=r$时$f$可以直接由$S$得到。总复杂度降至$O(mt\log^2t)$。
实现时细节很多,要注意DP边界条件和FFT下标变换。

代码

/*
 * Your nature demands love and your happiness depends on it.
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 55;
static int const M = 105;
static int const T = 100000;
static double const PI = acos(-1);
int rev[T];

class Point {
public:
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  std::pair<double, double> pair() {
    return std::make_pair(x, y);
  }
  friend Point operator+(Point const &a, Point const &b) {
    return Point(a.x + b.x, a.y + b.y);
  }
  friend Point operator-(Point const &a, Point const &b) {
    return Point(a.x - b.x, a.y - b.y);
  }
  friend Point operator*(Point const &a, Point const &b) {
    return Point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
  }
  Point operator/(double const &n) {
    return Point(x / n, y / n);
  }
} wn[T], A[T], B[T];

int init(int n) {
  int m = n, l = 0;
  for (n = 1; n <= m; n <<= 1, ++l)
    ;
  for (int i = 1; i < n; ++i)
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
  for (int i = 0; i < n >> 1; ++i)
    wn[i] = Point(cos(2 * PI / n * i), sin(2 * PI / n * i));
  return n;
}

void fft(Point *a, int n, int inv = 0) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i])
      std::swap(a[i], a[rev[i]]);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i << 1)
      for (int k = 0; k < i; ++k) {
        Point x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
        a[j + k] = x + y, a[j + k + i] = x - y;
      }
  if (inv) {
    std::reverse(a + 1, a + n);
    for (int i = 0; i < n; ++i)
      a[i] = a[i] / n;
  }
}

int n, m, t, x, mp[N][N];
double p[M][T], s[M][T], f[N][T];
struct Line {
  int a, b, c;
} li[M];

void update(int l, int r) {
  int mid = l + r >> 1, len = init(r - l + r - mid - 2);
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j < len; ++j)
      A[j] = B[j] = 0;
    for (int j = mid + 1; j <= r; ++j)
      A[j - mid - 1] = f[li[i].b][r - j + mid + 1];
    for (int j = 1; j <= r - l; ++j)
      B[j - 1] = p[i][j];
    fft(A, len), fft(B, len);
    for (int j = 0; j < len; ++j)
      A[j] = A[j] * B[j];
    fft(A, len, 1);
    for (int j = l; j <= mid; ++j)
      s[i][j] += A[r - j - 1].x;
  }
}

void solve(int l, int r) {
  if (l == r) {
    for (int i = 1; i <= m; ++i)
      f[li[i].a][l] = std::min(f[li[i].a][l], s[i][l] + li[i].c);
    return;
  }
  int mid = l + r >> 1;
  solve(mid + 1, r), update(l, r), solve(l, mid);
}

int main() {
  scanf("%d%d%d%d", &n, &m, &t, &x);
  memset(mp, 0x3f, sizeof mp);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &li[i].a, &li[i].b, &li[i].c);
    mp[li[i].a][li[i].b] = std::min(mp[li[i].a][li[i].b], li[i].c);
    for (int j = 1; j <= t; ++j)
      scanf("%lf", &p[i][j]), p[i][j] /= 100000;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      for (int k = 1; k <= n; ++k)
        mp[j][k] = std::min(mp[j][k], mp[j][i] + mp[i][k]);
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= t << 1; ++j)
      if (i == n)
        if (j <= t)
          f[i][j] = 0;
        else
          f[i][j] = x;
      else
        if (j <= t)
          f[i][j] = 1e9;
        else
          f[i][j] = x + mp[i][n];
  update(0, t << 1), solve(0, t), printf("%.8lf\n", f[1][0]);
  return 0;
}

Ellipse

题目描述

Math is important!! Many students failed in 2+2’s mathematical test, so let’s AC this problem to mourn for our lost youth..
Look at this sample picture:
A Ellipse
An ellipse in a plane centered on point $O$. The $L, R$ lines will be vertical through the $X$-axis. The problem is calculating the blue intersection area. But calculating the intersection area is dull, so I have to turn to you, a talent of programmer. Your task is telling me the result of calculation. (defined $\pi=3.14159265$, the area of an ellipse $A=\pi ab$)

题意概述

给定$a, b, l, r$,求椭圆${x^2 \over a^2}+{y^2 \over b^2}=1$在直线$x=l$与$x=r$之间的面积。
数据范围:$-a \le l \le r \le a$。

算法分析

这是一个不规则图形,无法直接计算,但我们可以用积分来求面积。设$f(n)$表示直线$x=n$与椭圆的两个交点之间的距离。
根据辛普森公式
$$
\int_a^b f(x) \, {\rm d}x \approx {b-a \over 6} \left(f(a)+4f\left({a+b \over 2}\right)+f(b)\right)
$$
但这样的精度并不是很高。考虑二分,令
$$g(l, r)=\int_l^r f(x) \, {\rm d}x, \; h(l, r)={r-l \over 6} \left(f(l)+4f\left({l+r \over 2}\right)+f(r)\right)$$
当$h(l, r)$与$h\left(l, {l+r \over 2}\right)+h\left({l+r \over 2}, r\right)$的差足够小时,令
$$g(l, r)=h(l, r)$$
否则
$$g(l, r)=g\left(l, {l+r \over 2}\right)+g\left({l+r \over 2}, r\right)$$
这样就可以达到精度要求。

代码

/*
 * Today is what happened to yesterday.
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

static double const EPS = 1e-8;
int a, b;

double get_y(double x) { return 2 * b * sqrt((1 - x * x / a / a)); }

double get_s(double l, double r) {
  return (get_y(l) + 4 * get_y((l + r) / 2) + get_y(r)) * (r - l) / 6;
}

double calc(double l, double r) {
  double mid = (l + r) / 2;
  if (fabs(get_s(l, r) - get_s(l, mid) - get_s(mid, r)) < EPS)
    return get_s(l, r);
  return calc(l, mid) + calc(mid, r);
}

int main() {
  int T;
  scanf("%d", &T);
  for (; T--;) {
    int l, r;
    scanf("%d%d%d%d", &a, &b, &l, &r);
    printf("%.3lf\n", calc(l, r));
  }
  return 0;
}

Clever Y

题目描述

Little Y finds there is a very interesting formula in mathematics:
$$
X^Y \bmod Z=K
$$
Given $X, Y, Z$, we all know how to figure out $K$ fast. However, given $X, Z, K$, could you figure out $Y$ fast?

题意概述

给定$X, Z, K$,求满足$X^Y \bmod Z=K$的$Y$的最小值。若不存在$0 \le Y \lt Z$满足条件,则输出无解。
数据范围:$0 \le X, Z, K \le 10^9$。

算法分析

显然$K \ge Z$时无解。在其他情况下,条件可以写成
$$
X^Y \equiv K \pmod Z
$$
特殊处理两种情况:$X, K$中至少有一个为$0$时,$Y=1$或无解;$K=1$时,$Y=0$。
先考虑$(X, Z)=1$的情况。令$M=\lceil \sqrt{Z} \rceil, \; Y=aM-b \; (0 \lt a, b \le M)$,那么
$$
\begin{align}
X^{aM-b} &\equiv K \pmod Z \\
X^{aM} &\equiv K \cdot X^b \pmod Z
\end{align}
$$
可以在$O(M)$的时间内预处理出$K \cdot X^b$,存在哈希表中,接着$O(M)$枚举$a$,判断哈希表中是否存在$X^{aM}$,若存在,则找到解$Y=aM-b$。由于要求最小值,因此哈希表中有重复时应记录较大的$b$。
下面考虑$(X, Z) \gt 1$的情况。令$D=(X, Z)$,易知若$K \nmid D$则无解。设$X=Dx, \; K=Dk, \; Z=Dz$,据同余的性质可得
$$
\begin{align}
(Dx)^Y &\equiv Dk \pmod{Dz} \\
x \cdot (Dx)^{Y-1} &\equiv k \pmod z
\end{align}
$$
因为$D=(X, Z)$,所以$(x, z)=1$,即$x$在模$z$意义下有逆元,因此
$$
(Dx)^{Y-1} \equiv k \cdot x^{-1} \pmod z
$$
令$X’=Dx=X, \; Y’=Y-1, \; K’=k \cdot x^{-1}, \; Z’=z$,则
$$
(X’)^{Y’} \equiv K’ \pmod{Z’}
$$
这和初始时的方程具有一样的形式。若$(X’, Z’) \gt 1$,则重复以上过程,否则可以参照$(X, Z)=1$的情况。

代码

/*
 * You will be singled out for promotion in your work.
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

class HashTable {
private:
  static int const MOD = 3214567;
  int numr, h[MOD], id[MOD], val[MOD], nxt[MOD];

public:
  void clear() { memset(h, numr = 0, sizeof h); }

int count(int const &n) {
    for (int i = h[n % MOD]; i; i = i[nxt])
      if (i[id] == n)
        return 1;
    return 0;
  }

int &operator[](int const &n) {
    for (int i = h[n % MOD]; i; i = i[nxt])
      if (i[id] == n)
        return i[val];
    ++numr, numr[id] = n, numr[nxt] = h[n % MOD], h[n % MOD] = numr;
    return numr[val];
  }
} mp;

int ex_gcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  int ret = ex_gcd(b, a % b, y, x);
  y -= a / b * x;
  return ret;
}

int get_gcd(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y);
}

int get_inv(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y), (x + b) % b;
}

int bsgs(int a, int b, int c) {
  a %= c;
  if (a == 0)
    return b == 0 ? 1 : -1;
  if (b == 0)
    return -1;
  if (b == 1)
    return 0;
  int k = 0;
  for (int t; (t = get_gcd(a, c)) > 1; ++k) {
    if (b % t)
      return -1;
    c /= t, b /= t, b = 1ll * b * get_inv(a / t, c) % c;
  }
  mp.clear();
  int d = a, m = sqrt(c) + 1;
  for (int i = 1; i <= m; ++i, d = 1ll * d * a % c)
    mp[1ll * d * b % c] = i;
  d = 1ll * d * get_inv(a, c) % c;
  int e = d;
  for (int i = 1; i <= m; ++i, e = 1ll * e * d % c)
    if (mp.count(e))
      return i * m - mp[e] + k;
  return -1;
}

int main() {
  for (int a, b, c; scanf("%d%d%d", &a, &c, &b), a || b || c;) {
    int ans = bsgs(a, b, c);
    if (~ans)
      printf("%d\n", ans);
    else
      puts("No Solution");
  }
  return 0;
}

Ceizenpok’s Formula

题目描述

Dr. Ceizenp’ok from planet i1c5l became famous across the whole Universe thanks to his recent discovery – the Ceizenpok’s formula. This formula has only three arguments: $n, k$ and $m$, and its value is a number of $k$-combinations of a set of $n$ modulo $m$.
While the whole Universe is trying to guess what the formula is useful for, we need to automate its calculation.

题意概述

求${n \choose k} \bmod m$。
数据范围:$1 \le n \le 10^{18}, \; 0 \le k \le n, \; 2 \le m \le 10^6$。

算法分析


$$
x={n \choose k}, \; m=p_1^{a_1}p_2^{a_2} \cdots p_q^{a_q}
$$
可以列出方程组
$$
\left\{
\begin{array}{c}
x \equiv r_1 \pmod{p_1^{a_1}} \\
x \equiv r_2 \pmod{p_2^{a_2}} \\
\cdots \\
x \equiv r_q \pmod{p_q^{a_q}}
\end{array}
\right.
$$
由于模数两两互质,所以该方程组在模$m$意义下有唯一解。
考虑如何求$r_i$。实际上,我们要求的就是${n \choose k} \bmod p_i^{a_i}$。我们知道
$$
{n \choose k}={n! \over k!(n-k)!}
$$
那么只要求出$n! \bmod p_i^{a_i}, \; k! \bmod p_i^{a_i}, \; (n-k)! \bmod p_i^{a_i}$的值,就可以用逆元求出${n \choose k} \bmod p_i^{a_i}$。
对于如何求$n! \bmod p_i^{a_i}$,令
$$
f(n)=n! \bmod p_i^{a_i}
$$
由$x \equiv x+p_i^{a_i} \pmod{p_i^{a_i}}$,可得
$$
f(n)=\left(f\left(\left\lfloor{n \over p_i}\right\rfloor\right)\cdot p_i^{\lfloor n/p_i \rfloor}\cdot\left(\prod_{i \in [1, p_i^{a_i}], \; p_i\not\mid i}i\right)^{\lfloor n/p_i^{a_i} \rfloor}\cdot\prod_{i \in [1, n \bmod p_i^{a_i}], \; p_i\not\mid i}i\right)\bmod p_i^{a_i}
$$
但是$k!, \; (n-k)!$在模$p_i^{a_i}$意义下可能不存在逆元,因此需要将$n!, \; k!, \; (n-k)!$中的$p_i$因子提取出来,求出逆元后再乘回去。
这样就得到了所有$r_i$。用中国剩余定理求解方程组即可。

代码

/*
 * Your lucky number has been disconnected.
 */

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

int power(int a, int b, int m) {
  int ret = 1;
  for (; b; b >>= 1)
    b & 1 && ((ret *= a) %= m), (a *= a) %= m;
  return ret;
}

void ex_gcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  ex_gcd(b, a % b, y, x), y -= a / b * x;
}

int get_inv(int a, int b) {
  int x, y;
  ex_gcd(a, b, x, y);
  return (x + b) % b;
}

int get_fac(int n, int p, int k) {
  int m = power(p, k, 1e9), ret = 1;
  for (; n; n /= p) {
    if (n / m) {
      int rec = 1;
      for (int i = 2; i < m; ++i)
        if (i % p)
          (rec *= i) %= m;
      (ret *= power(rec, n / m, m)) %= m;
    }
    for (int i = n % m; i > 1; --i)
      if (i % p)
        (ret *= i) %= m;
  }
  return ret;
}

int calc(int N, int K, int M, int p, int k) {
  int a = get_fac(N, p, k), b = get_fac(K, p, k), c = get_fac(N - K, p, k),
      cnt = 0;
  for (int i = N; i; i /= p)
    cnt += i / p;
  for (int i = K; i; i /= p)
    cnt -= i / p;
  for (int i = N - K; i; i /= p)
    cnt -= i / p;
  int m = power(p, k, 1e9),
      ret = a * get_inv(b, m) % m * get_inv(c, m) % m * power(p, cnt, m) % m;
  return ret * (M / m) % M * get_inv(M / m, m) % M;
}

signed main() {
  int N, K, M, ans = 0;
  scanf("%lld%lld%lld", &N, &K, &M);
  for (int i = 2, t = M; t > 1; ++i)
    if (!(t % i)) {
      int k = 0;
      for (; !(t % i); ++k, t /= i)
        ;
      (ans += calc(N, K, M, i, k)) %= M;
    }
  printf("%lld\n", ans);
  return 0;
}

Strange Way to Express Integers

题目描述

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:

  • Choose $k$ different positive integers $a_1, a_2, \ldots, a_k$. For some non-negative $m$, divide it by every $a_i$ to find the remainder $r_i$. If $a_1, a_2, \ldots, a_k$ are properly chosen, $m$ can be determined, then the pairs $(a_i, r_i)$ can be used to express $m$.

“It is easy to calculate the pairs from $m$,” said Elina. “But how can I find $m$ from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?

题意概述

给定同余方程组
$$
\left\{
\begin{array}{c}
x \equiv r_1 \pmod{a_1} \\
x \equiv r_2 \pmod{a_2} \\
\cdots \\
x \equiv r_k \pmod{a_k}
\end{array}
\right.
$$
求$x$的最小非负整数解。
数据范围:所有输入输出均可以表示为64位整型。

算法分析

对于两个方程
$$
\begin{align}
x &\equiv r_1 \pmod{a_1} \\
x &\equiv r_2 \pmod{a_2}
\end{align}
$$
考虑将它们合并。易知
$$
x=r_1+k_1a_1=r_2+k_2a_2
$$
移项得
$$
k_1a_1=r_2-r_1+k_2a_2
$$
由贝祖定理可知,这个方程有整数解的充要条件为$(a_1, a_2) \mid r_2-r_1$。方程两边同时除以$(a_1, a_2)$
$$
\begin{align}
k_1{a_1 \over (a_1, a_2)}&={r_2-r_1 \over (a_1, a_2)}+k_2{a_2 \over (a_1, a_2)} \\
k_1{a_1 \over (a_1, a_2)} &\equiv {r_2-r_1 \over (a_1, a_2)} \pmod{{a_2 \over (a_1, a_2)}} \\
k_1 &\equiv \left( {a_1 \over (a_1, a_2)} \right)^{-1} \cdot {r_2-r_1 \over (a_1, a_2)} \pmod{{a_2 \over (a_1, a_2)}}
\end{align}
$$
将其代回$x=r_1+k_1a_1$,得
$$
x \equiv r_1+k_1a_1 \pmod{{a_1a_2 \over (a_1, a_2)}}
$$
至此已成功将两个方程合并为一个相同形式的方程。

代码

/*
 * Your life would be very empty if you had nothing to regret.
 */

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

int ex_gcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  int ret = ex_gcd(b, a % b, y, x);
  y -= a / b * x;
  return ret;
}

int get_gcd(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y);
}

int get_inv(int a, int b) {
  int x, y;
  return ex_gcd(a, b, x, y), (x += b) %= b;
}

signed main() {
  for (int k, a, r; ~scanf("%lld%lld%lld", &k, &a, &r);) {
    int flag = 0;
    for (int ai, ri; --k;) {
      scanf("%lld%lld", &ai, &ri);
      int gcd = get_gcd(a, ai);
      if ((r - ri) % gcd)
        flag = 1;
      r += get_inv(a / gcd, ai / gcd) * ((ri - r) / gcd) % (ai / gcd) * a;
      (a /= gcd) *= ai, ((r %= a) += a) %= a;
    }
    if (flag)
      puts("-1");
    else
      printf("%lld\n", r);
  }
  return 0;
}