NOIP2021 模拟赛

A.翻转

• 计数题。注意到，998244353为质数，因此求逆元，费马小定理，AC
  附代码：

#include<bits/stdc++.h>
using namespace std;
const long long M=998244353;
long long n,k;
long long ans=1;
long long aa,bb,cc,dd;
long long jc(long long xx) {
    long long s=1;
    for(long long k=1; k<=xx; k++) {
        s*=k;
        s%=M;
    }
    return s;
}
long long jcc(long long xy) {
    long long ss=1;
    for(long long kk=1; kk<=xy; kk+=2) {
        ss*=kk;
        ss%=M;
    }
    return ss;
}
int pw(long long a, long long nn) {
    if (nn == 0)
        return 1;
    else if (nn % 2 == 1)
        return pw(a, nn - 1)%M * (a%M)%M;
    else {
        long long temp = pw(a, nn / 2)%M;
        return (temp * temp)%M;
    }
}
int main() {
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
    cin>>n>>k;
    aa=jc(n+k)%M;
    bb=jcc(2*k-1)%M;
    cc=jc(2*k)%M;
    dd=jc(n-k)%M;
    cout<<(aa*bb%M)*pw(cc*dd,M-2)%M;
    return 0;
}

B.数据结构

• 主席树维护，询问二分答案

C.不等

• 对不起，不会

D.约数

• 打表找规律，将数转化为向量，建图，跑floyd，再打表，跑BFS，AC

总结

• 好难啊