求问正确性

SuperCowHorse @ 2024-11-30 19:45:15

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const ll mod=1e9+7;
inline ll QPow(ll x,ll y,ll p){
    ll res=1;
    for(;y;y>>=1,x=x*x%p){
        if(y&1) res=res*x%p;
    }
    return res;
}
ll n,v,V,ans,a[maxn];int m;
map<ll,ll>mp;
inline ll Calc(ll n){
    return (QPow(v,n+1,mod)-1)*V%mod;
}
inline void solve(){
    scanf("%lld%d%lld",&n,&m,&v);
    mp.clear();V=QPow(v-1,mod-2,mod);
    for(int i=1;i<=m;++i){
        ll x,y;scanf("%lld%lld",&x,&y);
        if(mp[x]!=0&&mp[x]!=y){
            printf("0\n");
            return;
        }
        mp[x]=y;a[i]=x;
    }
    sort(a+1,a+1+m);m=unique(a+1,a+1+m)-a-1;
    ans=QPow(v,2*(a[1]-1),mod);
    for(int i=2;i<=m;++i){
        ll o=a[i]-a[i-1];
        ll res=(v-1)*(Calc(o*2-1)-Calc(o-1))%mod;
        if(res<mod) res+=mod;
        res=(res+QPow(v,o-1,mod));
        ans=ans*res%mod;
    }
    if(a[m]!=n){
        a[++m]=n;
        for(int i=m;i<=m;++i){
            ll o=a[i]-a[i-1];
            ll res=(v-1)*(Calc(o*2-1)-Calc(o-1))%mod;
            if(res<mod) res+=mod;
            res=(res+QPow(v,o,mod));
            ans=ans*res%mod;
        }
    }
    printf("%lld\n",ans);
}
signed main(){
    freopen("assign2.in","r",stdin);
    freopen("assign.out","w",stdout);
    int T;for(scanf("%d",&T);T;--T) solve();
    return 0;
}

by SuperCowHorse @ 2024-11-30 19:45:37

下面的freopen请自动无视

by 2024yourfather @ 2024-11-30 20:13:02

for(int i=1;i<=m;++i){
        ll x,y;scanf("%lld%lld",&x,&y);
        if(mp[x]!=0&&mp[x]!=y){
            printf("0\n");
            return;
        }
        mp[x]=y;a[i]=x;
    }

第6行没读完就退出了，可能有问题。

by huanglihuan @ 2024-11-30 20:21:55

@2024yourfather 1，亲测是这个问题

by huanglihuan @ 2024-11-30 20:23:02

@SuperCowHorse

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const ll mod=1e9+7;
inline ll QPow(ll x,ll y,ll p){
    ll res=1;
    for(;y;y>>=1,x=x*x%p){
        if(y&1) res=res*x%p;
    }
    return res;
}
ll n,v,V,ans,a[maxn];int m;
map<ll,ll>mp;
inline ll Calc(ll n){
    return (QPow(v,n+1,mod)-1)*V%mod;
}
inline void solve(){
    scanf("%lld%d%lld",&n,&m,&v);
    mp.clear();V=QPow(v-1,mod-2,mod);
    bool f=0;
    for(int i=1;i<=m;++i){
        ll x,y;scanf("%lld%lld",&x,&y);
        if(mp[x]!=0&&mp[x]!=y&&f==0){
            printf("0\n");
            f=1;
        }
        mp[x]=y;a[i]=x;
    }
    if(f==1)return;
    sort(a+1,a+1+m);m=unique(a+1,a+1+m)-a-1;
    ans=QPow(v,2*(a[1]-1),mod);
    for(int i=2;i<=m;++i){
        ll o=a[i]-a[i-1];
        ll res=(v-1)*(Calc(o*2-1)-Calc(o-1))%mod;
        if(res<mod) res+=mod;
        res=(res+QPow(v,o-1,mod));
        ans=ans*res%mod;
    }
    if(a[m]!=n){
        a[++m]=n;
        for(int i=m;i<=m;++i){
            ll o=a[i]-a[i-1];
            ll res=(v-1)*(Calc(o*2-1)-Calc(o-1))%mod;
            if(res<mod) res+=mod;
            res=(res+QPow(v,o,mod));
            ans=ans*res%mod;
        }
    }
    printf("%lld\n",ans);
}
signed main(){
//  freopen("assign2.in","r",stdin);
//  freopen("assign.out","w",stdout);
    int T;for(scanf("%d",&T);T;--T) solve();
    return 0;
}

by SuperCowHorse @ 2024-11-30 20:29:04

@huanglihuan 完啦

by SuperCowHorse @ 2024-11-30 20:31:00

@huanglihuan 大概会挂几分呜呜呜

by huanglihuan @ 2024-11-30 20:44:18

@SuperCowHorse 毕竟 T\le10，应该不会挂很多

by SuperCowHorse @ 2024-11-30 20:47:12

@huanglihuan 谢谢（我要开始每天烧香拜佛到12.9了）