NOIP2024 T2 题解

__vector__ · 2025-02-20 14:28:40 · 题解

Div.2 C 级别唐氏题，考场上为什么调了 3h+ 还没调出来呢？连 newbie 都能场切这题，我真的是 CM 吗？

首先排序去重，如果遇到条件自己冲突的那方案数就是 0。

按照已经确定的点将原序列 n 个位置划分为若干段，除了首段全部由不确定位置组成以外，每一段开头都是一个确定的位置。

• 首段不确定位置
  这一段的 a,b 随便填，只需要让 x_i \neq a_i，那么就显然是合法的。
• 除了首段，最后一段以外的段
  这类段的特点是第一个位置是确定的，段最后的下一个位置也是确定的。
  段的 a,b 方案书可以通过总方案数减去不合法方案数得到，令长度为 l。
  总方案数是 v^{2l}。
  不合法方案如何构造呢？显然只能是本段通过一些 a,b 的构造，强迫下一个确定位置的 x 值不等于其给定值。
  第一个位置有 v 的方案数确定第二个位置的值，第二个位置同样有 v 的方案数确定第三个位置的值。
  以此类推，总共有 v^{len-1} 的方案数确定本段最后一个位置的值。 本段最后一个位置总共有 v-1 的方案数（a 值等于自己，b 值不等于下一个位置）。 所以，总的不合法方案数是 v^{len-1}(v-1)。 总合法方案数是 v^{2len}-v^{len-1}(v-1)。
• 最后一段
  显然 a,b 随便填。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const ll mod=1e9+7;
int n,m,v;
pii lim[100005];
ll qpow(ll a,ll b){
//  printf("qpow %lld %lld\n",a,b);
    ll ret=1;
    for(;b;a=a*a%mod,b>>=1){
        if(b&1)ret=ret*a%mod;
    }
//  printf("ret %lld\n",ret);
    return ret;
}
void solve(int id_of_test){
    read(n);
    read(m);
    read(v);
    FOR(i,1,m){
        read(lim[i].fi);
        read(lim[i].se);
    }
    sort(lim+1,lim+m+1);
    m=unique(lim+1,lim+m+1)-lim-1;
    FOR(i,1,m-1){
        if(lim[i].fi==lim[i+1].fi){
            if(lim[i].se!=lim[i+1].se){
                puts("0");
                return;
            }
        }
    }
    ll ans=1;
    ans=ans*qpow(v,2*(lim[1].fi-1));
    ans=ans*qpow(v,2*(n-lim[m].fi))%mod;
    FOR(i,1,m-1){
        ll res=qpow(v,2*(lim[i+1].fi-lim[i].fi));
    //  printf("pre %lld [%d,%d]\n",res,lim[i].fi,lim[i+1].fi);
        res-=qpow(v,lim[i+1].fi-lim[i].fi-1)*(v-1)%mod;
    //  printf("fff %lld\n",res);
        ans=ans*res%mod;
    }
    printf("%lld\n",(ans+mod)%mod);
}
int main()
{
    int T;
    read(T);
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}