# 『ACM-XCPC』2020暑期ZJNU组队训练1

## 2020牛客暑期多校训练营（第一场）

Posted by GJ on July 12, 2020

## F Infinite String Comparision

Description

For a string x, Bobo defines x∞=xxx…, 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∞ and b∞ in lexicographical order.

You can refer the wiki page for further information of Lexicographical Order.

Input

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 ≤ a , b ≤ 105
• a, b consists of lower case letters.
• The total length of input strings does not exceed 2 × 106.

Output

For each test case, print “=” (without quotes) if a∞ = b∞ . Otherwise, print “<” if a∞ < b∞ , or “>” if a∞ > b∞ .

Sample Input

aa
b
zzz
zz
aba
abaa


Sample Output

<
=
>


Solution

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
string s, t;
int flag = 0;

int main() {
O_O;
while (cin >> s >> t) {
flag = 0;
int len = max(s.size(), t.size());
int les = s.length();
int let = t.length();
for (int i = 0; i < len*2; i++) {
if (s[i % les] > t[i % let]) { flag=1; break; }
else if (s[i % les] < t[i % let]) { flag=-1; break; }
}
if (flag == -1) cout << "<\n";
else if (!flag) cout << "=\n";
else cout << ">\n";
}
return 0;
}



## J Easy Integration

Description

Given n, find the value of $\int_{0}^1 (x - x^2)^n \mathrm{d} x$

It can be proved that the value is a rational number $\frac{p}{q}$.

Print the result as $(p · q^{-1}) \bmod 998244353$.

Input

The input consists of several test cases and is terminated by end-of-file.

Each test case contains an integer n.

* $1 \leq n \leq 10^6$ * The number of test cases does not exceed $10^5$.

Output

For each test case, print an integer which denotes the result.

Sample Input

1
2
3


Sample Output

166374059
432572553
591816295


Tips

 For n = 1,$\int_{0}^1 (x - x^2) \mathrm{d} x = \frac{x^2}{2} - \frac{x^3}{3} _0^1 = \frac{1}{6}$

Solution

n 分子 分母
1 1 6
2 2 60
3 6 840
4 24 15120
5 120 332640

$fz[n]=n!$

$fm[n]=fm[n-1](2i+1)*2$

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const ll mod = 998244353;
int n;
ll fz[maxn], fm[maxn];

void init() {
fz[0] = 1;
fm[1] = 6;
for (int i = 1; i <= 1e6; i++) fz[i] = fz[i - 1] * i % mod;
for (int i = 2; i <= 1e6; i++) fm[i] = fm[i - 1] * 2 * (2 * i + 1) % mod;
}

ll mul(ll a, ll b, ll p) {
long long res = 1;
a %= p;
while (b) {
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}

ll inv(ll a, ll b, ll mod) {
return a % mod * mul(b, mod - 2, mod) % mod;
}

int main() {
O_O;
init();
while (cin >> n) {
cout << inv(fz[n], fm[n], mod) << "\n";
}
return 0;
}



## I 1 or 2

Description

Bobo has a graph with n vertices and m edges where the i-th edge is between the vertices $a_i$ and $b_i$. Find out whether is possible for him to choose some of the edges such that the i-th vertex is incident with exactly $d_i$ edges.

Input

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains two integers n and m. The second line contains n integers $d_1$,$d_2$,$\dots$, $d_n$ . The i-th of the following m lines contains two integers $a_i$ and $b_i$ .

• $1 \leq n \leq 50$
• $1 \leq m \leq 100$
• $1 \leq d_i \leq 2$

• $1 \leq a_i, b_i \leq n$

• $a_i \neq b_i$

• ${a_i, b_i} \neq {a_j, b_j}$ for $i \neq j$

• The number of tests does not exceed 100.

Output

For each test case, print “Yes” without quotes if it is possible. Otherwise, print “No” without quotes.

Sample Input

2 1
1 1
1 2
2 1
2 2
1 2
3 2
1 1 2
1 3
2 3


Sample Output

Yes
No
Yes


Solution