长乐一中 Day 8 2023/7/22

Posted on By KMP

今天都是什么抽象东西啊

不会数论。试着重学，重学失败。

我数学一直都很烂的。

矩阵快速幂

T1

今天唯一搞懂的一题，感觉和矩阵没啥关系。

直接推公式然后算即可，记得特判p=1的情况。

code：

#include
#define int long long
using namespace std;
const int mod=998244353;
int p,k,pwn,pwn1,a,b;
int ansx=1,ansy=0;
int qpow(int n,int x){
    int ret=1;
    while (x){
        if (x&1){
            ret=ret*n%mod;
        }
        n=n*n%mod;
        x>>=1;
    }
    return ret;
}
void exgcd(int x,int y){
    if (!y){
        return;
    }
    exgcd(y,x%y);
    int lansx=ansx;
    ansx=ansy;
    ansy=lansx-x/y*ansy;
    return;
}
signed main()
{
    freopen("coin.in","r",stdin);
    freopen("coin.out","w",stdout);
    scanf("%lld%lld",&p,&k);
    if (p==1){
        printf("%lld",k);
        return 0;
    }
    pwn=qpow(p,k);
    pwn1=qpow(p,k+1);
    a=pwn-1;
    b=pwn1-pwn;
    exgcd(b,mod);
    ansx=(ansx%mod+mod)%mod*a%mod;
    printf("%lld",ansx);
    return 0;
}

T2

推公式的过程可以搞懂，但是搞不懂那个矩阵是咋搞出来的，网上也找不到讲构造这个矩阵的题解。昨天我翻ybt的时候就对构造矩阵感到非常的奇怪但是ybt上也并没有对方法的详细说明。

我啥也不会。

upd 2023-07-23 11:10:18 星期日：

去大搜特搜了一下构造矩阵的方法终于搜出来并且搞懂了。大概就是把每项的系数写出来就行。

code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int g0,g1,mod,n;
struct matrix{
    int mtr[3][3];
}ans,ret;
matrix operator * (const matrix &x,const matrix &y){
    matrix mul;
    memset(mul.mtr,0,sizeof mul.mtr);
    for (int i=0;i<3;i++){
        for (int j=0;j<3;j++){
            for (int k=0;k<3;k++){
                mul.mtr[i][j]=(x.mtr[i][k]*y.mtr[k][j]%mod+mul.mtr[i][j])%mod;
            }
        }
    }
    return mul;
}
void init(){
    ans.mtr[0][0]=sqrt(3+g0*g1);
    ans.mtr[0][1]=g1;
    ans.mtr[0][2]=g0;
    ret.mtr[0][0]=1;
    ret.mtr[1][0]=1;
    ret.mtr[2][0]=0;
    ret.mtr[0][1]=2;
    ret.mtr[1][1]=1;
    ret.mtr[2][1]=1;
    ret.mtr[0][2]=0;
    ret.mtr[1][2]=1;
    ret.mtr[2][2]=0;
    return;
}
matrix qpow(matrix x,int k){
    while (k){
        if (k&1){
            ret=ret*x;
        }
        x=x*x;
        k>>=1;
    }
    return ret;
}
signed main()
{
    freopen("fib.in","r",stdin);
    freopen("fib.out","w",stdout);
    scanf("%d%d%d%d",&g0,&g1,&mod,&n);
    if (n==0){
        printf("%d",g0);
        return 0;
    }
    if (n==1){
        printf("%d",g1);
        return 0;
    }
    init();
    ans=ans*qpow(ret,n-1);
    printf("%d",ans.mtr[0][2]);
    return 0;
}

T3

什么抽象东西

质数与约数

T1题解看不懂，T2看懂了但由于自己匮乏的知识储备没有完全看懂，T3看懂了但是完全不会打。

我是弱智。

训练日志