矩阵快速幂求助
查看原帖
矩阵快速幂求助
214728
剑雪清寒楼主2022/11/8 20:15

rt,不知为何寄了

#include <bits/stdc++.h>
using namespace std;
inline long long read() {
    long long x;bool f;char ch;
    for(f=0;!isdigit(ch=getchar());f=ch=='-');
    for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
    return f?-x:x;
}
inline void print(long long x,char las) {
    if(!x) {
        putchar(48),putchar(las);
        return ;
    }
    if(x<0) putchar('-'),x=-x;
    char ls[20];int k=0;
    while(x) ls[++k]=x%10+48,x/=10;
    while(k) fwrite(ls+k,1,1,stdout),k--;
    fwrite(&las,1,1,stdout);
    return ;
}
const long long p=19260817;
struct MAT {
    long long mat[3][3];
    inline MAT() {
        for(int i=0;i<3;i++) for(int j=0;j<3;j++) mat[i][j]=0;
    }
    inline MAT operator*(const MAT&ls) const {
        MAT res;int r;
        for(int i=0;i<3;i++)
            for(int k=0;k<3;k++) {
                long long r=mat[i][k];
                for(int j=0;j<3;j++) (res.mat[i][j]+=(r*ls.mat[k][j]))%=p;
            }
        return res;
    }
}zy,cs;
inline MAT ksm(MAT a,long long b) {
    MAT res;
    for(int i=0;i<3;i++) res.mat[i][i]=1;
    while(b) {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int m=read();long long qu[11];
int main() {
	for(int i=1;i<=m;i++) qu[i]=read();
	sort(qu+1,qu+m+1);
	cs.mat[0][0]=zy.mat[0][0]=zy.mat[0][1]=zy.mat[1][0]=zy.mat[2][0]=zy.mat[1][2]=1;
	// cs=cs*ksm(zy,3);
	// for(int i=0;i<3;i++) print(cs.mat[0][i],' ');
	// print(cs.mat[0][0]+cs.mat[0][1]+cs.mat[0][2]+cs.mat[0][3],'\n');
	for(int i=1;i<=m;i++) {
		cs=cs*ksm(zy,qu[i]-qu[i-1]);
		print(cs.mat[0][0]+cs.mat[0][1]+cs.mat[0][2],'\n');
	}
    return 0;
}
2022/11/8 20:15
加载中...