考场的思路，自认为比较清楚。

没有其它要求，一个二元限制的可能数为 $v^2$。

先只考虑一个区间，它的左右端点有限制，现在要求这个区间可行的方案数。若这个区间的长度可以放下 $x$ 个二元限制（不说长度为 $x+1$ 是因为可能会描述不清），设其方案数为 $f(x)$。

如果第一个二元限制的第一个数与左端点的数相同，那么这种情况有 $v$ 个可能的二元限制，同时下一个数也是有限制的，而剩下的方案数其实就是 $f(x-1)$，由乘法原理得此时的总方案数是 $v\times f(x-1)$。

如果第一个二元限制的第一个数与左端点的数不同，那么由于 $v\ge2$，第二个数一定有方法和第二个二元限制的第一个数不同。以此类推，后面的只要不踩中二元限制的第一个数，都一定有方法把这个区间所有数全部填上。因此，只要第一个二元限制的第一个数与左端点的数不同，剩下的二元限制随便选，都一定是有解的。剩下 $x-1$ 个二元限制方案数为 ${(v^{2})}^{(x-1)}=v^{2x-2}$，第一个由于不能和左端点相同所以是 $v\times(v-1)$，乘起来得到 $v\times(v-1)\times v^{2x-2}=v^{2x}-v^{2x-1}$。

把这两种情况加起来就能得到正确的递推式子：$f(x)=v^{2x}-v^{2x-1}+v\times f(x-1)$。

当然边界情况是 $f(1)=v^2-v+1$，即二元限制的第一个数与左边的数不同的 $v(v-1)$ 种情况，加上这两个数相同则右边的两个数也必须相同的 $1$ 种情况。

好的，先别急着直接开始写代码递推，看看继续推式子能不能推出点什么。

$$f(x)=v^{2x}-v^{2x-1}+v\times(v^{2x-2}-v^{2x-3}+v\times f(x-2))$$$$f(x)=v^{2x}-v^{2x-1}+v^{2x-1}-v^{2x-2}+v^2\times f(x-2)$$$$f(x)=v^{2x}-v^{2x-2}+v^2\times f(x-2)$$

嗯？好像有点东西，继续推推看？

$$f(x)=v^{2x}-v^{2x-2}+v^2\times(v^{2x-4}-v^{2x-5}+v\times f(x-3))$$$$f(x)=v^{2x}-v^{2x-2}+v^{2x-2}-v^{2x-3}+v^3\times f(x-3)$$$$f(x)=v^{2x}-v^{2x-3}+v^3\times f(x-3)$$

没错，经过推理我们得到了 $f(x)=v^{2x}-v^{2x-k}+v^k\times f(x-k)$。接着带入 $k=x-1$：

$$\begin{aligned}f(x)&=v^{2x}-v^{x+1}+v^{x-1}\times (v^2-v+1)\\&=v^{2x}-v^{x+1}+v^{x+1}-v^x+v^{x-1}\\&=v^{2x}-v^x+v^{x-1}\end{aligned}$$

套上个快速幂，$f(x)$ 就能 $O(\log x)$ 求出了。

最终答案是每两个限制之间的区间的情况数相乘，还要再乘上开头和末尾连续段的答案：

• 对于开头，因为没有左端点的限制，只要避免踩中任何一个二元限制就可以填出。所以这一段的二元限制是什么都没关系。答案为 $v^{2x}$。
• 对于末尾，因为没有右端点的限制，所以如果有二元限制就按着二元限制填，没有就随便填，也一定可以把这里的数填出。所以这一段的二元限制是什么也没关系。答案为 $v^{2x}$。

把所有区间的答案乘起来再输出即可，记得取模。算上刚开始需要的排序，时间复杂度为 $O(Tm(\log n+\log m))$，其中的 $\log n$ 是快速幂带来的。

这里会有一些对题解内容的补充以及赛时代码。 补充：

所以实际上每个一元限制具体的数字是没用的。

除了需要判断是不是存在矛盾的一元限制以外。

如果存在矛盾的一元限制记得需要特判输出零。

---

赛后编写的比较还原赛时代码的代码（可以通过民间数据）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7,N=1e5+5;
pair<int,int>a[N];
int ksm(int a,int b,int p){
	int s=1;
	while(b){
		if(b&1)s*=a,s%=p;
		a*=a;a%=p;
		b>>=1;
	}
	return s;
}
int f(int v,int x){
	int ans=ksm(v,x*2,mod);
	ans+=mod;
	ans-=ksm(v,x,mod);
	ans%=mod;
	ans+=ksm(v,x-1,mod);
	ans%=mod;
	return ans;
}
int mian(){
	int n,m,v;cin>>n>>m>>v;
	for(int i=1;i<=m;i++){
		cin>>a[i].first>>a[i].second;
	}
	sort(a+1,a+1+m);
	int ans=1;
	for(int i=2;i<=m;i++){
		if(a[i].first==a[i-1].first){
			if(a[i].second!=a[i-1].second){
				cout<<"0\n";
				return 0;
			}else continue;
		}
		ans*=f(v,a[i].first-a[i-1].first);ans%=mod;
	}
	ans*=ksm(v,2*(a[1].first-1),mod);ans%=mod;
	ans*=ksm(v,2*(n-a[m].first),mod);ans%=mod;
	cout<<ans<<"\n";
	return 0;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	while(t--)mian(); 
	return 0;
}

赛时代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;//v^2 - v + 1    **2<=v**
const int M=1e5+5;
ll ksm(ll a,ll b,ll p){
	ll s=1;
	while(b){
		if(b&1)s*=a,s%=p;
		a*=a,a%=p; 
		b>>=1;
	}
	return s;
}
using pii=pair<ll,ll>;
pii a[M];
ll f(int v,int x){
	int ans=0;
	ans+=ksm(v,x*2,mod);
	ans%=mod;
	ans+=mod;
	ans-=ksm(v,x,mod);
	ans%=mod;
	ans+=ksm(v,x-1,mod);
	ans%=mod;
	return ans;
}
int mian(){
	int n,m,v;//没有思路
	cin>>n>>m>>v;
	// f(x) = (v-1)*v * v^2 * v^2 * ...zheliyou(x-1)gev^2 + f(x-1)*v
	// f(1)=v^2-v+1
	// f(x) = (v-1) * v^{2x-1} + v * f(x-1)
	//但是还是太慢
	// f(x) = v^{2x} - v^{2x-1} + v * f(x-1)
	// f(x) = v^{2x} - v^{2x-1} + v * (v^{2x-2} - v^{2x-3} + v * f(x-2))
	// f(x) = v^{2x} - v^{2x-1} + v^{2x-1} - v^{2x-2} + v^2 * f(x-2)
	// f(x) = v^{2x} - v^{2x-2} + v^2 * f(x-2)
	// f(x) = v^{2x} - v^{2x-2} + v^2 * (v^{2x-4} - v^{2x-5} + v * f(x-3))
	// f(x) = v^{2x} - v^{2x-2} + v^{2x-2} - v^{2x-3} + v^3 * f(x-3)
	// f(x) = v^{2x} - v^{2x-3} + v^3 * f(x-3)
	// f(x) = v^{2x} - v^{2x-k} + v^k * f(x-k)
	// f(x) = v^{2x} - v^{2x-(x-1)} + v^{x-1} * f(1)
	// f(x) = v^{2x} - v^{x+1} + v^{x-1} * (v^2-v+1)
	// f(x) = v^{2x} - v^{x+1} + v^{x+1}-v^x+v^{x-1}
	// f(x) = v^{2x} - v^x + v^{x-1}
	for(int i=1;i<=m;i++){
		cin>>a[i].first>>a[i].second;
	}
	sort(a+1,a+1+m);
	//开头和末尾呢
	// v^{2x} 完事 
	ll ans=1;
	for(int i=2;i<=m;i++){
		int x=a[i].first-a[i-1].first;
		if(x==0){
			if(a[i].second==a[i-1].second)continue;
			else{
				cout<<0<<"\n";
				return 0;
			}
		}
		ans*=f(v,x);
		ans%=mod;
	}
	ans*=ksm(v,(a[1].first-1)*2,mod);ans%=mod;
	ans*=ksm(v,(n-a[m].first)*2,mod);ans%=mod;
	cout<<ans<<"\n";
	return 0;
}
int main(){
//	system("FC assign3.out assign3.ans");//后两个样例太棒了 
	ios::sync_with_stdio(0);cin.tie(0);
	freopen("assign.in","r",stdin);
	freopen("assign.out","w",stdout);//10：00 整 可能 过了？阳历都对 
	int t;cin>>t;while(t--)mian();
	return 0;
}
//baixie aqua
//baixie aqua