P11362 [NOIP2024] 遗失的赋值

Wild_Of_The_World · 2024-12-27 21:42:14 · 个人记录

反方向的钟

事实证明就算知道正解我也不一定写的出来

ans=a%MOD等于没模 =(a%MOD)

尽量模块化，别写一堆

40pts：

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const int MOD=1e9+7;
const int M=1e5+5;
ll n,m,v,ans,f[M];
struct xz{
    ll c,b;
}x[M];
bool cmp(xz a,xz b){return a.c<b.c;}
ll js;
ll qpow(ll a,ll b){
    if(b==1) return a;
    if(b==0) return 1;
    if(b%2!=0) return qpow(a,b-1)*a;
    js=qpow(a,b/2);
    return js*js;
}
ll fun(ll v,ll x){
    ll ans=0;
    ans+=qpow(v,2*x);
    ans%=MOD;
    ans-=qpow(v,x);
    ans%=MOD;
    ans+=qpow(v,x-1);
    ans%=MOD;
    return ans;
}
void work(){
    ans=1;
    cin>>n>>m>>v;
    for(int i=1;i<=m;i++)   cin>>x[i].c>>x[i].b;
    sort(x+1,x+1+m,cmp);
    for(int i=2;i<=m;i++){
        if(x[i].c==x[i-1].c){
            if(x[i].b!=x[i-1].b){
                cout<<0<<endl;
//              cout<<"QAQ"<<endl;
                return ;
            }
            continue;
        }
        ans*=fun(v,x[i].c-x[i-1].c),ans%=MOD;
    }   
    ans*=qpow(v,2*(x[1].c-1));
    ans*=qpow(v,2*(n-x[m].c));
    cout<<ans<<endl;
    return ;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    cin>>t;
    while(t--) work();
    return 0;
}

一堆小问题

100pts：

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
const ll MOD=1e9+7;
const int M=1e5+5;
ll n,m,v,ans,f[M];
struct xz{
    ll c,b;
}x[M];
bool cmp(xz a,xz b){return a.c<b.c;}
ll js;
ll qpow(ll a,ll b){
    if(b==1) return a;
    if(b==0) return 1;
    if(b%2!=0) return qpow(a,b-1)*a%MOD;
    js=qpow(a,b/2)%MOD;
    return js*js%MOD;
}
ll fun(ll v,ll x){
    ll ans=0;
    ans+=qpow(v,2*x);
    ans%=MOD;
    ans+=MOD;
    ans-=qpow(v,x);
    ans%=MOD;
    ans+=qpow(v,x-1);
    ans%=MOD;
    return ans;
}
void work(){
    ans=1;
    cin>>n>>m>>v;
    for(int i=1;i<=m;i++)   cin>>x[i].c>>x[i].b;
    sort(x+1,x+1+m,cmp);
    for(int i=2;i<=m;i++){
        if(x[i].c==x[i-1].c){
            if(x[i].b!=x[i-1].b){
                cout<<0<<endl;
//              cout<<"QAQ"<<endl;
                return ;
            }
            continue;
        }
        ans*=fun(v,x[i].c-x[i-1].c),ans%=MOD;
    }   
    ans*=qpow(v,2*(x[1].c-1))%MOD;
    ans%=MOD;
    ans*=qpow(v,2*(n-x[m].c))%MOD;
    ans%=MOD;
    cout<<ans<<endl;
    return ;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    cin>>t;
    while(t--) work();
    return 0;
}