2020年牛客多校-第一场

前言：
不会网络流的菜鸡就做出来了F和J(Worlfram + oeis),还是太菜，好好学习，早日刷完网络流24题。

F. Infinite String Comparision
题意：
For a string x, Bobo defines x^{\infty}=xxx_{\cdot \cdot \cdot} which is x repeats for infinite times, resulting in a string of infinite length.
Bobo has two strings a and b. Find out the result comparing a^{\infty} and b^{\infty}in lexicographical order.

输入描述：
The input consists of several test cases terminated by end-of-file.

The first line of each test case contains a string a, and the second line contains a string b.

• $1 \leqslant \left| a \right|,\left| b \right|\leqslant 10^5$
• a, b consists of lower case letters.
• The total length of input strings does not exceed 2 * 10^6

输出描述：

For each test case, print "=" (without quotes) if a^{\infty}=b^{\infty}. Otherwise, print "<" if a^{\infty}<b^{\infty}, or ">" if a^{\infty}>b^{\infty}

输入：

aa
b
zzz
zz
aba
abaa

输出：

<
=
>

题解：
比较两个字符串可以一直迭代自身的字典序大小，只需每个字符串扩大2倍，再补成一样长度大小比较即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define mem(a, b) memset(a, b, sizeof(a))
#define Fast_IO ios::sync_with_stdio(false);
#define inf 0x3f3f3f3f
const int maxn = 3e6 + 10;
const int maxm = 5e5 + 10;
const ll mod = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-8;

void solve(string s,string t){
    s += s;
    t += t;
    int len1 = s.size();
    int len2 = t.size();
    if(len1 > len2){
      int k = len1 - len2;
      for(int i = len2; i < len2 + k; i ++)
        t += t[(i - len2) % len2];
      // cout <<"---"<< s << " " << t << endl;
      if(s == t)  puts("=");
      else if(s > t)  puts(">");
      else  puts("<");
    }
    else if(len1 < len2){
      int k = len2 - len1;
      for(int i = len1; i < len1 + k; i ++)
        s += s[(i - len1) % len1];
      // cout <<"--"<< s << " " << t << endl;
      if(s == t)  puts("=");
      else if(s > t)  puts(">");
      else  puts("<");
    }
    else{
      if(s == t)  puts("=");
      else if(s > t)  puts(">");
      else  puts("<");
    }
}
int main(){
    //srand((unsigned)time(0));
    //freopen("out.txt","w",stdout);
    //freopen("in.txt","r",stdin);
    string s,t;
    while(cin >> s >> t){
        solve(s,t);
    }
    return 0;
}

J. Easy Integration
题意：
Given n, find the value of \int_0^1{\left( x-x^2 \right) ^ndx} It can be proved that the value is a rational number \frac{p}{q} Print the result as \left( p\cdot q^{-1} \right) \ mod \ 998244353

输入描述：
The input consists of several test cases and is terminated by end-of-file.
Each test case contains an integer n.

• $1\leqslant n\leqslant 10^6$
• The number of test cases does not exceed 10^5

输出描述：
For each test case, print an integer which denotes the result.

输入：

1
2
3

输出：

166374059
432572553
591816295

题解：
不正经解法：Wolfram + Oeis 查表得公式:

$$
\frac{n!^2}{\left( 2n+1 \right) !}
$$

预处理阶乘+快速幂求逆元。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rlld(a) scanf("%lld", &a)
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define mem(a, b) memset(a, b, sizeof(a))
#define Fast_IO ios::sync_with_stdio(false);
#define inf 0x3f3f3f3f
const int maxn = 3e6 + 10;
const int maxm = 5e5 + 10;
const ll mod = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-8;

ll n, k;

ll fact[maxn];
ll inv[maxn];

ll quickpow(ll a, ll b, ll mod)
{
    ll ans = 1 % mod;
    while(b)
        {
            if(b & 1)
                ans = ans * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
    return ans;
}

void init(){
    fact[0] = 1;
     for(int i = 1;i < maxn ;i ++)
       fact[i] = fact[i - 1] * i % mod;
    inv[maxn - 1] = quickpow(fact[maxn - 1], mod - 2, mod);
    for(int i = maxn - 2; i >= 0; i --)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}

int main(){
  ll n;
  init();
  while(~rlld(n)){
    ll  ans = quickpow(fact[n], 2ll, mod) % mod;
    printf("%lld\n", ans * quickpow(fact[2 * n + 1], mod - 2, mod) % mod);
  }
  return 0;
}

A. B-Suffix Array
题目链接：https://ac.nowcoder.com/acm/contest/5666/A

题意：给一个长度为n的字符串，通过给定的函数变成一个b序列，求b的所有后缀子串升序排列。

大佬题解：https://blog.csdn.net/weixin_43965698/article/details/107304525

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define mem(a, b) memset(a, b, sizeof(a))
#define rd(a) scanf("%d", &a)
#define rs(a) scanf("%s", a)
#define al(x)  x + 1, x + 1 + n
#define inf 0x3f3f3f3f
const int maxn = 2e5 + 10;
const int maxm = 5e5 + 10;
const ll mod = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-8;

int n, m;
char s[maxn];
int t[maxn], sa[maxn], rk[maxn], c[maxn], y[maxn];

struct node{
  int x, y;
  bool operator<(const node &rhs)const{
    if(y - x == rhs.y - rhs.x)
      return rk[y + 1] < rk[rhs.y + 1];
    return y - x < rhs.y - rhs.x;
  }
}seg[maxn];

void get_sa()
{
  for(int i = 1; i <= m; i ++)  c[i] = 0;
  for(int i = 1; i <= n; i ++)  ++ c[rk[i] = t[i]];
  for(int i = 2; i <= m; i ++)  c[i] += c[i - 1];
  for(int i = n; i >= 1; i --)  sa[c[rk[i]] --] = i;

  for(int k = 1; k <= n; k <<= 1){
    int num = 0;
    for(int i = n - k + 1; i <= n; i ++)  y[++ num] = i;
    for(int i = 1; i <= n; i ++)
      if(sa[i] > k) y[++ num] = sa[i] - k;
    for(int i = 1; i <= m; i ++)  c[i] = 0;
    for(int i = 1; i <= n; i ++)  ++ c[rk[i]];
    for(int i = 2; i <= m; i ++)  c[i] += c[i - 1];
    for(int i = n; i >= 1; i --)
      sa[c[rk[y[i]]] --] = y[i], y[i] = 0;

    rap(i, 1, n)  y[i] = rk[i];

    rk[sa[1]] = 1;
    num = 1;
    for(int i = 2; i <= n; i ++)
      rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;

    if(num == n)  break;
    m = num;
  }
}

int main()
{
  // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
  while(~rd(n)){
    rs(s + 1);
    int pa = - 1, pb = -1;
    mem(t, 0);
    rap(i, 1, n){
      t[i] = 0;
      sa[i] = 0;
      if(s[i] == 'a'){
        if(pa != -1) t[i] = i - pa;
        pa = i;
      }
      else{
        if(pb != -1) t[i] = i - pb;
        pb = i;
      }
    }
    rap(i, 1, n)  t[i] ++;
    m = n;
    get_sa();
    pa = pb = n + 1;
    for(int i = n; i >= 1; i --){
      if(s[i] == 'a'){
        seg[i] = {i, pb};
        pa = i;
      }
      else{
        seg[i] = {i, pa};
        pb = i;
      }
    }

    rk[n + 1] = -1;
    rk[n + 2] = -2;
    sort(al(seg));
    rap(i, 1, n){
      printf("%d ", seg[i].x);
    }
    puts("");
  }
  return 0;
}

这题有个结论，答案等价于对f\left[ i \right] =\min _{j>i,s\left[ j \right] =s\left[ i \right]}\left( j-i \right)求后缀排序，如果对应的后面没有出现s\left[ i \right]则f\left[ i \right]=inf,把后缀排序翻转就是答案。
如abaab=231\infty \infty这个后缀排序为31245,翻转及为答案。
有兴趣可以搜索论文Parameterized\ Suffix\ Arrays\ for\ Binary\ Strings
反正我比赛时是想不到这么牛逼的结论（
代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define lap(i, n, a) for(int i=n; i>=a; i--)
#define mem(a, b) memset(a, b, sizeof(a))
#define rd(a) scanf("%d", &a)
#define rs(a) scanf("%s", a)
#define al(x)  x + 1, x + 1 + n
#define inf 0x3f3f3f3f
const int maxn = 2e5 + 10;
const int maxm = 5e5 + 10;
const ll mod = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-8;

int n, m;
char s[maxn];
int t[maxn], sa[maxn], rk[maxn], c[maxn], y[maxn];

void get_sa()
{
  for(int i = 1; i <= m; i ++)  c[i] = 0;
  for(int i = 1; i <= n; i ++)  ++ c[rk[i] = t[i]];
  for(int i = 2; i <= m; i ++)  c[i] += c[i - 1];
  for(int i = n; i >= 1; i --)  sa[c[rk[i]] --] = i;

  for(int k = 1; k <= n; k <<= 1){
    int num = 0;
    for(int i = n - k + 1; i <= n; i ++)  y[++ num] = i;
    for(int i = 1; i <= n; i ++)
      if(sa[i] > k) y[++ num] = sa[i] - k;
    for(int i = 1; i <= m; i ++)  c[i] = 0;
    for(int i = 1; i <= n; i ++)  ++ c[rk[i]];
    for(int i = 2; i <= m; i ++)  c[i] += c[i - 1];
    for(int i = n; i >= 1; i --)
      sa[c[rk[y[i]]] --] = y[i], y[i] = 0;

    rap(i, 1, n)  y[i] = rk[i];

    rk[sa[1]] = 1;
    num = 1;
    for(int i = 2; i <= n; i ++)
      rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;

    if(num == n)  break;
    m = num;
  }
}

int main()
{
  // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
  while(~rd(n)){
    rs(s + 1);
    int pa = - 1, pb = -1;
    mem(t, 0);
    lap(i, n, 1){
      t[i] = 0; sa[i] = 0; y[i] = 0;
      if(s[i] == 'a'){
        if(pa != -1) t[i] = pa - i;
        else  t[i] = n;
        pa = i;
      }
      else{
        if(pb != -1) t[i] = pb - i;
        else  t[i] = n;
        pb = i;
      }
    }
    n ++;
    t[n] = n;
    m = n;
    get_sa();

    lap(i, n - 1, 1){
      printf("%d ", sa[i]);
    }
    puts("");
  }
  return 0;
}