本文共 6265 字，大约阅读时间需要 20 分钟。

写在前面

良心出题人zhx！！！！

预估成绩：\(100+100+100+70 = 370pts\)

• 排名第三竟只是一个二等？
• 感觉发的耳机贼像机房的耳机，顿时没有鼠标香了/kk
• gryz人均获奖/cy
• 被rk1的jijidawang单调队列了/kk （就评论三楼那位/qq
• 想要rk1的键盘/kel

T1

高精度取模

把字符串倒过来读，边读边取模即可

/*Work by: Suzt_ilymicsKnowledge: ??Time: O(??)*/#include
   
    #include
    
     #include
     
      #include
      
       #define int long long#define LL long long#define orz cout<<"lkp AK IOI!"<
       
        << 1) + (s << 3) + ch - '0' , ch = getchar();	return f ? -s : s;}signed main(){    cin >> (s + 1), y = read();    int len = strlen(s + 1);    for(int i = 1; i <= len; ++i) a[i] = s[len - i + 1] - '0';    if(len == 0) {        for(int i = len; i >= 1; --i) x = x * 10 + a[i];        printf("%lld\n", x % y);    } else {        for(int i = len; i >= 1; --i) {            x = x * 10 + a[i];            x %= y;        }        printf("%lld\n", x);    }	return 0;}
       
      
     
    
   

T2

Description：

数据范围：\(n,m \le 10^9\)

Solution：

考虑没有颜色的情况：

只有 \(20pts\)，考虑涂上颜色。

因为每种颜色可以随便涂，所以一个方块的方案数为 \(m\)，发现两次转移都会增加三个块，所以方案数要乘以 \(m^3\)，转移方程改为：

现在有 \(70pts\) 了。

发现这个式子很像斐波那契的递推式啊，考虑矩阵加速。列出相关式子，求出转移矩阵

其中 \(Base\) 为

矩阵快速幂转移就好了

/*Work by: Suzt_ilymicsKnowledge: ??Time: O(??)f[i] = f[i - 2] * 2 + f[i - 1] // f[i] 表示 到第 i 列 的方案数（不计颜色） f[i] = f[i - 2] * 2 * m^3 + f[i - 1] * m^3; // 计颜色，两种转移路径都会增加三个方块，每个方块有m种选择方案 1 12 0*/#include
   
    #include
    
     #include
     
      #include
      
       #define int long long#define LL long long#define orz cout<<"lkp AK IOI!"<
       
        << 1) + (s << 3) + ch - '0' , ch = getchar();	return f ? -s : s;}//void work1() {//    f[1] = 1, f[2] = 3;//    for(int i = 3; i <= n; ++i) f[i] = (2 * f[i - 2] + f[i - 1]) % mod;//    printf("%lld\n", f[n]);//}int Quick_Pow(int x, int p, int mod) {    int res = 1;    while(p) {        if(p & 1) res = res * x % mod;        x = x * x % mod;        p >>= 1;    }    return res;}Matrix Pow(Matrix x, int p) {    Matrix res;    for(int i = 1; i <= 2; ++i) res.a[i][i] = 1;    while(p) {        if(p & 1) res = res * x;        x = x * x;        p >>= 1;    }    return res;}signed main(){    n = read(), m = read();//    if(m == 1) work1();//    else if(n <= 1000000){//        f[1] = Quick_Pow(m, 3, mod);//        f[2] = Quick_Pow(m, 3, mod) * 2 + Quick_Pow(m, 6, mod);//        for(int i = 3; i <= n; ++i) {//            f[i] = (f[i - 2] * 2 % mod + f[i - 1]) % mod * f[1] % mod;//        }//        printf("%lld\n", f[n]);//    } else {        ans.a[1][1] = (Quick_Pow(m, 3, mod) * 2 + Quick_Pow(m, 6, mod)) % mod;        ans.a[1][2] = Quick_Pow(m, 3, mod);        if(n == 1) {            printf("%lld", ans.a[1][2]);            return 0;        }        if(n == 2) {            printf("%lld", ans.a[1][1]);            return 0;        }        base.a[1][1] = 1 * Quick_Pow(m, 3, mod) % mod, base.a[1][2] = 1;        base.a[2][1] = 2 * Quick_Pow(m, 3, mod) % mod, base.a[2][2] = 0;        Matrix Base = Pow(base, n - 2);        ans = ans * Base;        printf("%lld", ans.a[1][1] % mod);//    }	return 0;}/*100 100674167999520955619*/
       
      
     
    
   

T3

Description

Solution

\(C_n^m\) 在指数上啊

发现后面的模数是质数，所以可以用欧拉定理取模

但是 \(1000003470\) 是个合数，没法求逆元，所以我只写了 \(n,m \le 10^3\) 的递推部分/kk

发现 \(1000003470\) 可以分解为 \(2 \times 3 \times 5 \times 53 \times 677 \times 929\)

所以对于每个质数求一边，然后用中国剩余定理合并即可（或者用扩展卢卡斯）

嗯，我写挂了

/*Work by: Suzt_ilymicsKnowledge: ??Time: O(??)*/#include
   
    #include
    
     #include
     
      #include
      
       #define int long long#define LL long long#define orz cout<<"lkp AK IOI!"<
       
        << 1) + (s << 3) + ch - '0' , ch = getchar();	return f ? -s : s;}int Gcd(int a, int b) { return !b ? a : Gcd(b, a % b); }int Lcm(int a, int b) { return a / Gcd(a, b) * b; }void Merge(int &a1, int &m1, int a2, int m2) {    if(m1 < m2) swap(m1, m2), swap(a1, a2);    while(a1 % m2 != a2) a1 += m1;    m1 = Lcm(m1, m2);}int Quick_Pow(int x, int p, int mod) {    int res = 1;    while(p) {        if(p & 1) res = res * x % mod;        x = x * x % mod;        p >>= 1;    }    return res;} int C(int n, int m, int p) {    if(n < m) return 0;    return a[p][n][m];}int Lucas(int n, int m, int p) {     if(!m) return 1;    if(m > n) return 0;    return Lucas(n / tmp[p], m / tmp[p], p) * C(n % tmp[p], m % tmp[p], p) % tmp[p]; }void Init() {    for(int i = 0; i < 6; ++i) {        a[i][0][0] = 1;        for(int j = 1; j <= tmp[i]; ++j) {            for(int k = 0; k <= j; ++k) {                a[i][j][k] = a[i][j - 1][k - 1] + a[i][j - 1][k];                if(a[i][j][k] >= tmp[i]) a[i][j][k] -= tmp[i];            }        }    }}signed main(){    Init();    x = read(), n = read(), m = read();    for(int i = 0; i < 6; ++i) b[i] = Lucas(n, m, i);    int v1 = 0, n1 = 1;    for(int i = 0; i < 6; ++i) Merge(v1, n1, b[i], tmp[i]);    printf("%lld", Quick_Pow(x, v1, mod));	return 0;}
       
      
     
    
   

T4

Description

Solution

前三十分暴力判断；

\(N = 1\) 时输出两遍 \(a_1\) 即可；

发现 \(x\) 时不变的，所以存在一个合理的 \(x\) 是所有 \(a_i\) 的最小公倍数，又因为保证 \(y \le 10^3\) 然后枚举就变成 \(O(n^2)\) 的了，可以通过 \(70pts\)

正解不会了/kk

正解：发现对于每个 \(y\) 可以写成同余方程的形式，然后解这个同余方程组即可

• \(y-i+1\) 如果是负数注意转化成正数

/*Work by: Suzt_ilymicsKnowledge: ??Time: O(??)*/#include
   
    #include
    
     #include
     
      #include
      
       #define LL long long#define int long long#define orz cout<<"lkp AK IOI!"<
       
        << 1) + (s << 3) + ch - '0' , ch = getchar();	return f ? -s : s;}int Gcd(int a, int b) { return !b ? a : Gcd(b, a % b); }int Lcm(int a, int b) { return a / Gcd(a, b) * b; } void Merge(int &a1, int &m1, int a2, int m2) {    if(m1 < m2) swap(m1, m2), swap(a1, a2);    while(a1 % m2 != a2) a1 += m1;    m1 = Lcm(m1, m2);}signed main(){    n = read();    for(int i = 1; i <= n; ++i) a[i] = read();    for(int i = 1; i <= n; ++i) x = Lcm(x, a[i]);    for(int i = 1; i <= n; ++i) b[i] = ((a[i] - i + 1) % a[i] + a[i]) % a[i];    int v1 = 0, n1 = 1;    for(int i = 1; i <= n; ++i) Merge(v1, n1, b[i], a[i]);    printf("%lld %lld", x, v1);	return 0;}