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

(拿来监督自己补补题)

J.Easy Integration

n = 1 , r e s = 1 2 ∗ 3 n = 1,res=\frac{1}{2*3} 等价于 1 2 ∗ 3 \frac{1}{2*3}
n = 2 , r e s = 2 3 ∗ 4 ∗ 5 n=2,res=\frac{2}{3*4*5} 等价于 1 ∗ 2 3 ∗ 4 ∗ 5 \frac{1*2}{3*4*5}
n = 3 , r e s = 6 4 ∗ 5 ∗ 6 ∗ 7 n=3,res=\frac{6}{4*5*6*7} 等价于 1 ∗ 2 ∗ 3 4 ∗ 5 ∗ 6 ∗ 7 \frac{1*2*3}{4*5*6*7}

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

B ( P , Q ) = P + Q P Q C P + Q P = 1 Q C P + Q − 1 P − 1 B(P,Q)=\frac{P+Q}{PQC_{P+Q}^P}=\frac{1}{QC_{P+Q-1}^{P-1}}

#includebits/stdc++.h
using namespace std;

typedef long long LL;
typedef pairint, int PII;

const int p = 998244353;
const int N = 2e6 + 10;
LL fac[N], infac[N];
LL n;

LL kpow(LL a, LL n) {
LL res = 1;
while(n) {
if(n  1) res = (res * a) % p;
n = 1;
a = (a * a) % p;
}
return res;
}

void init() {
fac[0] = infac[0] = 1;
for(int i = 1; i  N; i++) {
fac[i] = (fac[i - 1] * i) % p;
infac[i] = (infac[i - 1] * kpow(i, p - 2)) % p;
}
}

LL C(int a, int b) {
return fac[a] * infac[b] % p * infac[a - b] % p;
}

void solve() {
printf("%lld\n", kpow(n + 1, p - 2) * kpow(C(2 * n + 1, n), p - 2) % p);
}

int main() {
init();
// freopen("in.txt", "r", stdin);
//int t; cin  t; while(t--)
while(~scanf("%d",n))
solve();
return 0;
}

F Infinite String Comparision

#includebits/stdc++.h
using namespace std;

int main() {
//    freopen("in.txt", "r", stdin);
string a, b;
while(cin  a  b) {
string A = a + b;
string B = b + a;
if(A  B) puts("");
else if(A == B) puts("=");
else puts("");
}
return 0;
}


I 1 or 2

#includebits/stdc++.h
using namespace std;

typedef pairint, int PII;
typedef long long LL;
const int N = 110, M = 410;
vectorint e[N];
int n, m;
int d[N];
int idx;
PII edge[N];
vectorint du[N];

bool Graph[M][M];
int Match[M];
bool InQueue[M], InPath[M], InBlossom[M];
int Queue[M];
int Start, Finish;
int NewBase;
int Father[M], Base[M];
int Count;

void init() {
for(int i = 1; i = n; i++) {
e[i].clear();
du[i].clear();
}
memset(d, 0, sizeof d);
memset(edge, 0, sizeof edge);
memset(Graph, 0, sizeof Graph);
memset(Match, 0, sizeof Match);
memset(InQueue, 0, sizeof InQueue);
memset(InPath, 0, sizeof InPath);
memset(InBlossom, 0, sizeof InBlossom);
memset(Queue, 0, sizeof Queue);
memset(Father, 0, sizeof Father);
memset(Base, 0, sizeof Base);
Count = Start = Finish = NewBase = Head = Tail = idx = 0;
}

void CreatGraph() {
for(int i = 1; i = n; i++) {
for(int j = 1; j = d[i]; j++) {
du[i].push_back(++idx);
}
}
for(int i = 1; i = m; i++) {
int u = edge[i].first, v = edge[i].second;
int a = ++idx, b = ++idx;
Graph[a][b] = Graph[b][a] = 1;
for(int j = 0; j  du[u].size(); j++) {
int x = du[u][j];
Graph[a][x] = Graph[x][a] = 1;
}
for(int j = 0; j  du[v].size(); j++) {
int x = du[v][j];
Graph[b][x] = Graph[x][b] = 1;
}
}
}

void Push(int u) {
Queue[Tail] = u;
Tail++;
InQueue[u] = true;
}

int Pop() {
return res;
}

int FindCommonAncestor(int u, int v) {
memset(InPath, false, sizeof(InPath));
while(true) {
u = Base[u];
InPath[u] = true;
if(u == Start) break;
u = Father[Match[u]];
}
while(true) {
v = Base[v];
if(InPath[v]) break;
v = Father[Match[v]];
}
return v;
}

void ResetTrace(int u) {
int v;
while(Base[u] != NewBase) {
v = Match[u];
InBlossom[Base[u]] = InBlossom[Base[v]] = true;
u = Father[v];
if(Base[u] != NewBase) Father[u] = v;
}
}

void BloosomContract(int u, int v) {
NewBase = FindCommonAncestor(u, v);
memset(InBlossom, false, sizeof(InBlossom));
ResetTrace(u);
ResetTrace(v);
if(Base[u] != NewBase) Father[u] = v;
if(Base[v] != NewBase) Father[v] = u;
for(int tu = 1; tu = idx; tu++) {
if(InBlossom[Base[tu]]) {
Base[tu] = NewBase;
if(!InQueue[tu]) Push(tu);
}
}
}

void FindAugmentingPath() {
memset(InQueue, false, sizeof(InQueue));
memset(Father, 0, sizeof Father);
for(int i = 1; i = idx; i++) Base[i] = i;
Push(Start);
Finish = 0;
int u = Pop();
for(int v = 1; v = idx; v++) {

if(Graph[u][v]  (Base[u] != Base[v])  (Match[u] != v)) {

if((v == Start) || ((Match[v]  0)  Father[Match[v]]  0)) {
BloosomContract(u, v);
}
else if(Father[v] == 0) {
Father[v] = u;
if(Match[v]  0) Push(Match[v]);
else {
Finish = v;
return;
}
}
}
}
}
}

void AugmentPath() {
int u, v, w;
u = Finish;
while(u  0) {
v = Father[u];
w = Match[v];
Match[v] = u;
Match[u] = v;
u = w;
}
}

void Edmonds() {
memset(Match, 0, sizeof Match);
for(int u = 1; u = idx; u++) {
if(Match[u] == 0) {
Start = u;
FindAugmentingPath();
if(Finish  0) AugmentPath();
}
}
}

void PrintMatch() {
Count = 0;
for(int u = 1; u = idx; u++) {
if(Match[u]  0) Count++;
}
if(Count == idx) puts("Yes");
else puts("No");
}

void solve() {
CreatGraph();
Edmonds();
PrintMatch();
}

int main() {
freopen("in.txt", "r", stdin);
while(~scanf("%d%d", n, m)) {
init();
for(int i = 1; i = n; i++) {
scanf("%d", d[i]);
}
for(int i = 1; i = m; i++) {
int u, v;
scanf("%d%d", u, v);
e[u].push_back(v);
e[v].push_back(u);
edge[i] = {u, v};
}
solve();
}
return 0;
}


• 03:19
• 03:49
• 06:55
• 01:42