题意分析
首先，$n$ 个变量显然会被 $m$ 条一元限制切割为若干段。
不考虑每一段的边界情况，段内一个变量的方案数显然为 $v^2$。
段内总方案数显然仅仅与段的长度有关，设长度为 $x$ 的段的方案数为 $f_x$。
考虑求出 $f_x$：
-
如果第一个变量与左端点相同，段内方案数显然为：
\[v\cdot f_{x-1}\]即相同有 $v$ 个可能的二元限制，剩下的 $x-1$ 个元素方案数为 $f_{x-1}$。
-
如果第一个变量与左端点不同，段内方案数为：
\[v(v-1)\cdot\left(v^2\right)^{x-1}=v^{2x}-v^{2x-1}\]即不同，有 $v(v-1)$ 个可能的二元限制，剩下的 $x-1$ 个无限制的元素的方案数为 $\left(v^2\right)^{x-1}$。
则有：
\[f_x=v^{2x}-v^{2x-1}+v\cdot f_{x-1}\]边界条件为：
\[f_1=v^2-v+1\]考虑到 $n\leq 10^9$，则 $x\leq 10^9$，$\mathcal O(n\log n)$ 递推（快速幂要带一个 $\log$）肯定会 $\text{TLE}$，因此考虑能否优化。
不妨先找一下规律：
\[\begin{aligned} f_x&=v^{2x}-v^{2x-1}+v\cdot f_{x-1}\\ &=v^{2x}-v^{2x-1}+v(v^{2(x-1)}-v^{2(x-1)-1}+v\cdot f_{x-2})\\ &=v^{2x}-v^{2x-1}+v^{2x-1}-v^{2x-2}+v^2\cdot f_{x-2}\\ &=v^{2x}-v^{2x-2}+v^2\cdot f_{x-2}\\ &\cdots\\ &=v^{2x}-v^{2x-3}+v^3\cdot f_{x-3}\\ &\cdots\\ &=v^{2x}-v^{2x-(x-1)}+v^{x-1}\cdot f_1\\ &=v^{2x}-v^x+v^{x-1} \end{aligned}\]规律即 $f_x=v^{2x}-v^{2x-k}+v^k\cdot f_{x-k}$，如果需要严谨证明，使用数学归纳法即可。
那么代入 $k=x-1$，有： \(f_x=v^{2x}-v^x+v^{x-1}\)
直接计算每一段的答案再相乘即可。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e9,M=1e5,V=1e9,P=1e9+7;
int n,m,v;
pair<int,int>a[M+1];
int qpow(int a,int n){
int base=a,ans=1;
while(n){
if(n&1){
ans=1ll*ans*base%P;
}
base=1ll*base*base%P;
n>>=1;
}
return ans;
}
int f(int x){
return (1ll*qpow(v,x<<1)-qpow(v,x)+qpow(v,x-1))%P;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n>>m>>v;
for(int i=1;i<=m;i++){
cin>>a[i].first>>a[i].second;
}
sort(a+1,a+m+1);
//无解
bool flag=false;
for(int i=1;i<=m;i++){
if(a[i].first==a[i-1].first&&a[i].second!=a[i-1].second){
cout<<"0\n";
flag=true;
break;
}
}
if(flag){
continue;
}
int ans=1ll*qpow(v,a[1].first-1<<1)*qpow(v,n-a[m].first<<1)%P;
for(int i=2;i<=m;i++){
if(a[i].first!=a[i-1].first){
ans=1ll*ans*f(a[i].first-a[i-1].first)%P;
}
}//答案非负
if(ans<0){
ans+=P;
}
cout<<ans<<'\n';
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
