求问考场做法正确性

Kevin_Lsy @ 2024-11-30 19:43:42

by hepp @ 2024-11-30 20:27:11

@Kevin_Lsy 总算碰到和我一样的了/kel

by Kevin_Lsy @ 2024-11-30 21:53:28

@hepp 同道中人（握手qwq

by Kevin_Lsy @ 2024-11-30 21:57:30

@hepp@hepp 用矩乘就多了个8倍常数qwq 我还开了int128(一开始以为是取模没取好)，是不是要被卡了/fn

by hepp @ 2024-12-01 09:36:28

@Kevin_Lsy它过了它过了

感谢喜欢卡常的自己

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7,N=1e5+10;
inline int read(){
    int x=0;char ch=getchar();bool fg=0;
    while(ch<'0'||ch>'9'){if(ch=='-')fg=1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch-'0'),ch=getchar();
    return (fg?(~(x-1)):x);
}
int T,n,m,v;
struct node{int c,d;};node k[N];
bool cmp(node x,node y){return x.c<y.c;}
struct sql{
    int a[2][2];
    void clr(){memset(a,0,sizeof(a));}
    void innt(){clr();a[0][0]=a[1][1]=1;}
};
void add(int &x,int y){
    x+=y;if(x>=mod) x-=mod; 
}
sql pls(sql x,sql y){
    sql z; z.clr();
    for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int f=0;f<=1;f++)
        add(z.a[i][j],x.a[i][f]*y.a[f][j]%mod);
    return z;
}
sql pw(sql x,int y){
    sql as;as.innt();
    while(y){
        if(y&1) as=pls(as,x);
        y>>=1,x=pls(x,x);
    }
    return as;
}
signed main()
{
    T=read();
    while(T--){
        int p=1;
        n=read(),m=read(),v=read();
        for(int i=1;i<=m;i++)
            k[i].c=read(),k[i].d=read();
        sort(k+1,k+m+1,cmp);
        sql y,ans;ans.clr(),y.clr();
        y.a[0][0]=v*v%mod;
        y.a[1][0]=v*(v-1)%mod;
        y.a[1][1]=v;
        if(k[1].c==1ll)
            ans.a[0][1]=1;
        else{
            ans.a[0][0]=1;
            ans=pls(ans,pw(y,k[1].c-1));
            ans.a[0][1]=ans.a[0][0],ans.a[0][0]=0;
        }
        for(int i=2;i<=m;i++){
            if(k[i].c==k[i-1].c&&k[i].d!=k[i-1].d){p=0;break;}
            if(k[i].c==k[i-1].c) continue;
            ans=pls(ans,pw(y,k[i].c-k[i-1].c-1));
            ans.a[0][1]=(ans.a[0][0]*v%mod*v%mod+ans.a[0][1]*((v*v-v+1)%mod)%mod)%mod,ans.a[0][0]=0;
        }
        int f=0;
        if(k[m].c==n)
            f=ans.a[0][1];
        else{
            ans=pls(ans,pw(y,n-k[m].c));
            add(f,ans.a[0][0]),add(f,ans.a[0][1]);
        }
        printf("%lld\n",f*p);
    }
    return 0;
}

by Kevin_Lsy @ 2024-12-01 10:12:57

@hepp %%%