problem A

由于$f_{i}=A+f_{i-1}+B+f_{i-1}+C$。所以$f_{i}$的串的长度会随着$i$的变大迅速变大。

因此，只需要暴力判断在A,B,C中还是在$f_{i-1}$中即可。

problem B

将开始的序列看作是$n$个0.然后每次插入一个数字$x$时，要么找到一个严格大于$x$的数字将其改为$x$，要么插入一个为0的位置上。前一种操作对每个位置最多进行$c-1$次，后一个操作需要$n$次。所以一共最多需要$(n-1)*c+1$次

为了减少操作，可以维护一个从前向后非减，从后向前非增的序列。也就是说，如果一个数字$x$小于等于$\frac{c}{2}$，那么从前向后找到一个大于$x$的将其改为$x$；否则从后向前找到一个小于$x$的将其改为$x$。这样的话，操作次数是$(n-1)*\left \lceil \frac{c}{2} \right \rceil+1$。

problem C

由于操作2的存在，那么一旦进行一次操作2，将会出现一大段连续相同的数字。即便再出现操作1，还是会有大段连续数字。因此，将连续数字存储成$(val,cnt)$即可。

problem D

首先枚举vip的数量$x$，那么首先需要为这$x$选取$x$个位置，为$C_{n}^{x}$。剩下的$n-x$是50和100的个数。

设$f(n,L,R)$表示$n$个50和100,最后剩余50的个数为$[L,R]$范围，满足这些的合法顺序的方案数。那么答案为：$answer=\sum_{i=0}^{n}f(n-i,L,R)C_{n}^{i}$

现在考虑如何计算$f(n,L,R)$。

首先假设$n$中50和100的个数相等的答案，即$f(n,0,0),n$为偶数。这样的合法序列可以看作一条从$(0,0)$到$(n,0)$的折线，从$(x_{i},y_{i})$到$(x_{i}+1,y_{i+1})$时，需满足$|y_{i}-y_{i+1}|=1$且$y_{i}\ge 0,y_{i+1}\ge 0$。所有的情况有$C_{n}^{\frac{2}{2}}$个。

但是这些中有不合法的情况。假设这条折线在$(x_{t},y_{t})$时第一次出现$y_{t}<0$的情况，即$y_{t}=-1$。现在将$(0,0)$到$x_{t},y_{t}$之间的折线部分按照直线$y=-1$作一个对称，那么现在的折线变成了从点$(0,-2)$到点$(n,0)$。

那么所有的从$(0,0)$到$(n,0)$的不合法的折线都会对应到一条从$(0,-2)$到点$(n,0)$的折线。而从$(0,-2)$到点$(n,0)$折线有$C_{n}^{\frac{n}{2}-1}$种（因为要选择$\frac{n}{2}-1$条向下）。所以$f(n,0,0)=C_{n}^{\frac{n}{2}}-C_{n}^{\frac{h}{2}-1}$。

进一步，现在考虑$f(n,h,h)$，$n,h$都是偶数。那么答案为$f(n,h,h)=C_{n}^{\frac{n}{2}-\frac{h}{2}}-C_{n}^{\frac{n}{2}-\frac{h}{2}-1}$。其中$C_{n}^{\frac{n}{2}-\frac{h}{2}}$是从$(0,0)$到$(n,h)$的折线数量，$C_{n}^{\frac{n}{2}-\frac{h}{2}-1}$是从$(-2,0)$到$(n,h)$的折线数量。

现在假设$n,L,R$都是偶数，那么有

$f(n,L,R)=\sum_{i \in [L,R],i=2k}f(n,i,i)$

$=\sum_{i \in [L,R],i=2k}C_{n}^{\frac{n}{2}-\frac{i}{2}}-C_{n}^{\frac{n}{2}-\frac{i}{2}-1}$

$=C_{n}^{\frac{n}{2}-\frac{L}{2}}-C_{n}^{\frac{n}{2}-\frac{R}{2}-1}$

那么对于任意的$n,L,R$有$f(n,L,R)=C_{n}^{\left \lfloor \frac{n-L}{2} \right \rfloor}-C_{n}^{\left \lceil \frac{n-R}{2} \right \rceil-1}$。比如$n=19,L=4,R=10$时，最后剩余50的个数只能取$5,7,9$，即与$n$的奇偶性相同

现在就是如何计算$C_{n}^{m}$%$p$.设$p=p_{1}^{a_{1}}...p_{k}^{a_{k}}$

由于$C_{n}^{m}=\frac{n!}{m!(n-m)!}$。那么计算$n!$%$p$时，先把$[1,n]$中每个数字中包含的$p_{i}$都去掉，这样就可以直接求乘法逆元了。

然后对于每个$p_{i}$，计算$n!,(n-m)!,m!$中含有的$p_{i}$的个数$x,y,z$ ,那么最后乘以$p_{i}^{x-y-z}$即可。

problem E

分块。每块内维护一个数组$A$，表示每个值的个数。

将每个大于$x$的数减去$x$相当于将所有小于等于$x$的值都加上$x$。然后整个区间的数字都减去$x$。

所以维护一个off值。表示该块内所有的数字都加上了off。

再维护一个[nMin,nMax]表示该块内个数大于0的数字的最大最小值。$nMin>off$。也就是说现在该块内最大的数字为$nMax-off$。

如果块中每个数字都加上$x$。分两种情况操作：

（1）$x$ 较小，即$nMin+x+x<nMax$，这时候将$[nMin,nMin+x-1]$都加上$x$，令$off=off+x,nMin=nMin+x$

（2）$x$较大，将$[nMin+x,nMax]$区间的数字都减去$x$,令$nMax=nMin+x-1$

这中间需要用一个并查集维护存储某个数字个数的真正位置。

查询整个块中$x$个数时，直接查询$x+off$个数即可。

不是整个区间的操作时都暴力进行即可。

code for problem A

import java.util.Scanner;public class Main {  String s = "What are you doing at the end of the world? Are you busy? Will you save us?";  String A = "What are you doing while sending \"";  String B = "\"? Are you busy? Will you send \"";  String C = "\"?";  long[] f = new long[61];  public static void main(String[] args) {    new Main().cal();  }  void cal() {    f[0] = s.length();    int t = A.length() + B.length() + C.length();    for (int i = 1; i <= 60; ++ i) {      f[i] = f[i - 1] * 2 + t;    }    Scanner in = new Scanner(System.in);    StringBuilder sb = new StringBuilder();    int q = in.nextInt();    for (int i = 0; i < q; ++ i) {      int n = in.nextInt();      long k = in.nextLong();      sb.append(get(n, k));    }    System.out.println(sb.toString());  }  char get(int n, Long k) {    int t = A.length();    while (n > 54) {      if (k <= t) {        return A.charAt(k.intValue() - 1);      }      k -= t;      n -= 1;    }    if (k > f[n]) {      return '.';    }    while (n > 0) {      if (k <= A.length()) {        return A.charAt(k.intValue() - 1);      }      k -= A.length();      if (f[n - 1] >= k) {        n -= 1;        continue;      }      k -= f[n - 1];      if (k <= B.length()) {        return B.charAt(k.intValue() - 1);      }      k -= B.length();      if (f[n - 1] >= k) {        n -= 1;        continue;      }      k -= f[n - 1];      return C.charAt(k.intValue() - 1);    }    return s.charAt(k.intValue() - 1);  }}

　　

code for problem B

import java.util.Scanner;public class Main {  public static void main(String[] args) {    new Main().cal();  }  int n;  int m;  int c;  int[] p = null;  void cal() {    Scanner in = new Scanner(System.in);    n = in.nextInt();    m = in.nextInt();    c = in.nextInt();    p = new int[n];    for (int i = 0; i < m; ++ i) {      int x = in.nextInt();      int pos = add(x);      p[pos] = x;      System.out.println(pos + 1);      System.out.flush();      if (finish()) {        return;      }    }  }  int add(int x) {    if (x <= c / 2) {      int id = 0;      while (p[id] != 0 && p[id] <= x) {        id ++;      }      return id;    }    else {      int id = n - 1;      while (p[id] != 0 && p[id] >= x) {        id --;      }      return id;    }  }  boolean finish() {    for (int i = 0; i < n; ++ i) {      if (p[i] == 0) {        return false;      }    }    return true;  }}

　　

code for problem C

import java.util.Arrays;import java.util.Comparator;import java.util.Scanner;public class Main {  public static void main(String[] args) {    new Main().cal();  }  static class Pair {    long val;    int cnt;    Pair() {}    Pair(long val, int cnt) {      this.val = val;      this.cnt = cnt;    }  }  static class PairComparator implements Comparator
     
       {    @Override    public int compare(Pair a, Pair b) {      return a.val < b.val ? -1 : 1;    }  }  int n;  int m;  int seed;  int vmax;  Pair[] b = null;  Pair[] c = null;  int bSize = 0;  int cSize = 0;  int rnd() {    int ret = seed;    seed = (int)((seed * 7L + 13) % 1000000007);    return ret;  }  void cal() {    Scanner in = new Scanner(System.in);    n = in.nextInt();    m = in.nextInt();    seed = in.nextInt();    vmax = in.nextInt();    b = new Pair[n];    c = new Pair[n];    b[bSize ++] = new Pair(rnd() % vmax + 1, 1);    for (int i = 2; i <= n; ++ i) {      int val = rnd() % vmax + 1;      if (val == b[bSize - 1].val) {        b[bSize - 1].cnt += 1;      }      else {        b[bSize ++] = new Pair(val, 1);      }    }    for (int i = 0; i < m; ++ i) {      int op = rnd() % 4 + 1;      int left = rnd() % n + 1;      int right = rnd() % n + 1;      if (left > right) {        int tmp = left;        left = right;        right = tmp;      }      int x = 0;      int y = 0;      if (op == 3) {        x = rnd() % (right - left + 1) + 1;      }      else {        x = rnd() % vmax + 1;      }      if (op == 4) {        y = rnd() % vmax + 1;      }      if (op == 1 || op == 2) {        operation1or2(left, right, x, op == 1);      }      else if (op == 3) {        operation3(left, right, x);      }      else  {        operation4(left, right, x, y);      }    }  }  void operation1or2(int left, int right, int x, boolean isOperation1) {    int L = 0, R = 0;    cSize = 0;    for (int i = 0; i < bSize; ++ i) {      L = R + 1;      R = L + b[i].cnt - 1;      add(b[i].val, intersect(L, left - 1, L, R));      if (isOperation1) {        add(b[i].val + x, intersect(left, right , L, R));      }      else {        add(x, intersect(left, right , L, R));      }      add(b[i].val, intersect(right + 1, R, L, R));    }    for (int i = 0; i <  cSize; ++ i) {      b[i] = c[i];    }    bSize = cSize;  }  void operation3(int left, int right, int kth) {    int L = 0, R = 0;    cSize = 0;    for (int i = 0; i < bSize; ++ i) {      L = R + 1;      R = L + b[i].cnt - 1;      int cnt = intersect(left, right , L, R);      if (cnt > 0) {        c[cSize ++] = new Pair(b[i].val, cnt);      }    }    Arrays.sort(c, 0, cSize, new PairComparator());    for (int i = 0; i < cSize; ++ i) {      if (c[i].cnt >= kth) {        System.out.println(c[i].val);        return;      }      kth -= c[i].cnt;    }  }  void operation4(int left, int right, int x, int y) {    int L = 0, R = 0;    long result = 0;    for (int i = 0; i < bSize; ++ i) {      L = R + 1;      R = L + b[i].cnt - 1;      int cnt = intersect(left, right , L, R);      if (cnt > 0) {        result += Pow(b[i].val, x, y) * cnt % y;        result %= y;      }    }    System.out.println(result);  }  int intersect(int left1, int right1, int left2, int right2) {    int left = Math.max(left1, left2);    int right = Math.min(right1, right2);    return Math.max(0, right - left + 1);  }  void add(long val, int cnt) {    if (cnt == 0) {      return;    }    if (cSize > 0 && c[cSize - 1].val == val) {      c[cSize - 1].cnt += cnt;    }    else {      c[cSize ++] = new Pair(val, cnt);    }  }  static long Pow(long a, int b, int mod) {    long result = 1;    a %= mod;    while (b != 0) {      if (b % 2 == 1) {        result = result * a % mod;      }      a = a * a % mod;      b >>= 1;    }    return result;  }}
     

　　

code for problem D

import java.util.*;public class Main {  public static void main(String[] args) {    new Main().cal();  }  int n;  int p;  int left;  int right;  long[] fact = null;  int[] primes = null;  void init() {    primes = split(p);    fact = new long[n + 1];    fact[0] = 1;    for (int i = 1; i <= n; ++ i) {      int k = i;      for (int prime : primes) {        while (k % prime == 0) {          k /= prime;        }      }      fact[i] = fact[i - 1] * k % p;    }  }  void cal() {    Scanner in = new Scanner(System.in);    n = in.nextInt();    p = in.nextInt();    left = in.nextInt();    right = in.nextInt();    if (p == 1) {      System.out.println(0);      return;    }    init();    long result = 0;    for (int cNum = 0; cNum <= n; ++ cNum) {      long t = calculate(cNum, (cNum + left + 1) / 2) - calculate(cNum, (cNum + right) / 2 + 1);      t %= p;      t *= calculate(n, cNum);      t %= p;      result += t;      result %= p;    }    if (result < 0) {      result += p;    }    System.out.println(result);  }  long calculate(int n, int m) {    if (m < 0 || m > n) {      return 0;    }    if (m == 0 || m == n) {      return 1;    }    long result = fact[n] * reverse(fact[m] * fact[n - m] % p, p) % p;    for (int prime : primes) {      int cnt = count(n, prime) - count(m, prime) - count(n - m, prime);      result = result * Pow(prime, cnt, p) % p;    }    return result;  }  static int count(int n, int p) {    int cnt = 0;    while (n > 0) {      cnt += n / p;      n /= p;    }    return cnt;  }  static long Pow(long a, long b, long mod) {    long result = 1;    while (b > 0) {      if (b % 2 == 1) {        result = result * a % mod;      }      a = a * a % mod;      b >>= 1;    }    return result;  }  static long reverse(long a, long b)  {    long[] r = exGcd(a,b);    return (r[1] % b + b) % b;  }  static long[] exGcd(long a,long b)  {    if (b == 0)    {      return new long[]{a, 1, 0};    }    long[] result = exGcd(b, a % b);    return new long[]{result[0], result[2], result[1] - a / b * result[2]};  }  static int[] split(int x) {    List
     
       list = new ArrayList<>();    for (int i = 2; i * i <= x; ++ i) {      if (x % i == 0) {        list.add(i);        while (x % i == 0) {          x /= i;        }      }    }    if (x > 1) {      list.add(x);    }    int[] result = new int[list.size()];    for (int i = 0; i < list.size(); ++ i) {      result[i] = list.get(i);    }    return result;  }}
     

code for problem E

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.*;public class Main {  public static void main(String[] args) {    new Main();  }  static class FastIO {    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));    PrintWriter out = new PrintWriter(System.out);    StringTokenizer st = null;    String nextToken() {      while (st == null || !st.hasMoreTokens()) {        try {          st = new StringTokenizer(bufferedReader.readLine());        }        catch (IOException e) {          throw new RuntimeException(e);        }      }      return st.nextToken();    }    int nextInt() {      return Integer.parseInt(nextToken());    }    void output(Object object) {      out.println(object);    }    void finish() {      out.close();    }  }  FastIO fastIO = new FastIO();  Main() {    cal();    fastIO.finish();  }  static class Block {    int nMin;    int nMax;    int left;    int right;    int off;    int[] parent = null;    int[] c = null;    Block(int left, int right, int[] a) {      this.left = left;      this.right = right;      this.off = 0;      nMin = 1;      nMax = Integer.MIN_VALUE;      for (int i = left; i <= right; ++ i) {        nMax = Math.max(nMax, a[i]);      }      parent = new int[nMax + 1];      c = new int[nMax + 1];      for (int i = left; i <= right; ++ i) {        c[a[i]] += 1;      }      for (int i = 0; i < nMax + 1; ++ i) {        parent[i] = i;      }    }    int getRoot(int x) {      if (parent[x] != x) {        parent[x] = getRoot(parent[x]);      }      return parent[x];    }    void rebuild(int L, int R, int[] a, int x) {      if (L == left && R == right) {        rebuildAll(x);        return;      }      for (int i = left; i <= right; ++ i) {        a[i] = getRoot(a[i]);      }      for (int i = L; i <= R; ++ i) {        if (a[i] - off > x) {          c[a[i]] -= 1;          a[i] -= x;          c[a[i]] += 1;        }      }    }    void rebuildAll(int x) {      if (nMax - nMin + 1 <= x) {        return;      }      if (nMin + x + x - 1 <= nMax) {        off += x;        for (int i = nMin; i < nMin + x; ++ i) {          parent[i] = i + x;          c[i + x] += c[i];          c[i] = 0;        }        nMin += x;      }      else {        for (int i = nMin + x; i <= nMax; ++ i) {          parent[i] = i - x;          c[i - x] += c[i];          c[i] = 0;        }        nMax = nMin + x - 1;      }    }    int query(int L, int R, int[] a, int x) {      if (L == left && R == right) {        return queryAll(x);      }      x += off;      int cnt = 0;      for (int i = L; i <= R; ++ i) {        if (getRoot(a[i]) == x) {          cnt += 1;        }      }      return cnt;    }    int queryAll(int x) {      if (nMin <= x + off && x + off <= nMax) {        return c[x + off];      }      return 0;    }  }  static final int BLOCK_SIZE = 333;  int n;  int m;  int[] a = null;  Block[] b = null;  void cal() {    n = fastIO.nextInt();    m = fastIO.nextInt();    a = new int[n];    for (int i = 0; i < n; ++ i) {      a[i] = fastIO.nextInt();    }    final int nBlockNum = (n - 1) / BLOCK_SIZE + 1;    b = new Block[nBlockNum];    for (int i = 0; i < nBlockNum; ++ i) {      int left = i * BLOCK_SIZE;      int right = Math.min(n - 1, left + BLOCK_SIZE - 1);      b[i] = new Block(left, right, a);    }    for (int i = 0; i < m; ++ i) {      int op = fastIO.nextInt();      int left = fastIO.nextInt() - 1;      int right = fastIO.nextInt() - 1;      int x = fastIO.nextInt();      int lBlockIndex = left / BLOCK_SIZE;      int rBlockIndex = right / BLOCK_SIZE;      if (op == 1) {        if (lBlockIndex == rBlockIndex) {          b[lBlockIndex].rebuild(left, right, a, x);        }        else {          b[lBlockIndex].rebuild(left, b[lBlockIndex].right, a, x);          b[rBlockIndex].rebuild(b[rBlockIndex].left, right, a, x);          for (int j = lBlockIndex + 1; j <= rBlockIndex - 1; ++ j) {            b[j].rebuildAll(x);          }        }      }      else {        int result = 0;        if (lBlockIndex == rBlockIndex) {          result += b[lBlockIndex].query(left, right, a, x);        }        else {          result += b[lBlockIndex].query(left, b[lBlockIndex].right, a, x);          result += b[rBlockIndex].query(b[rBlockIndex].left, right, a, x);          for (int j = lBlockIndex + 1; j <= rBlockIndex - 1; ++ j) {            result += b[j].queryAll(x);          }        }        fastIO.output(result);      }    }  }}