深圳网站制作公司售后_电子工程网校_搜索引擎广告案例_网络营销的好处和优势

$\text{[Problem Discription]}$

$\text{[Analysis]}$

疑似某退役 OIer 重新回归打 NOIP。

个人觉得比 T1 要简单，主要是贪心题是真的不敢写。

首先，我们可以发现：如果位置 $i$ 和 $(i+1)$ 都没有一元限制的话，那么可能的方案数就有 $v^2$ 种。

主要就来考虑 $i$ 或者 $(i+1)$ 有限制的情况。发现，好像还是 $v^2$ 种（在不都有限制的情况下）。所以，这样思考肯定是没有作用的。

那就考虑相邻的两个有限制的点之间的方案数。假设这相邻的两点为 $x$ 和 $y$（不妨设 $y>x$）。如果没有限制的话，那么这两点间的方案数应该是 $v^{2(y-x)}$。考虑不合法的二元限制的数量。

怎样的限制是不合法的呢？很显然是 $x$ 限制了 $(x+1)$ 取某个特定的值，$(x+1)$ 又限制 $(x+2)$，以此类推，直到 $(y-1)$ 限制 $y$ 的取值，且 $y$ 被限制的取值不为它被一元限制所规定的取值。

形式化地说，就是：

$$a_{\lambda }=d_x,b_{\lambda }\in [1,v]$$

$$a_{\lambda +1}=b_{\lambda },b_{\lambda +1}\in [1,v]$$

$$a_{\lambda +2}=b_{\lambda +1},b_{\lambda +2}\in [1,v]$$

$$\cdots$$

$$a_{\mu }=b_{\mu -1},b_{\mu }\in [1,v],b_{\mu }\ne d_y$$

用手指头即可知道不合法的方案数为 $(v-1)\times v^{y-x-1}$。

于是在区间 $[x,y]$ 中合法的方案数为 $v^{2(y-x)}-(v-1)\times v^{y-x-1}$。

分段累计即可。

注意特判同一条一元限制多次出现或相互排斥的一元限制出现的情况。

$\text{[Code]}$

int n,k,m,v,ans,T;struct Limits{int pos,val;bool operator < (const Limits t) const{return pos<t.pos;}
}lim_init[N],lim[N];int ksm(int a,int p){int res=1;while (p){if (p&1) res=1ll*res*a%mod;a=1ll*a*a%mod;p>>=1;}return res;
}void read_data(){n=read();k=read();v=read();for(int i=1;i<=k;i++){lim_init[i].pos=read();lim_init[i].val=read();}sort(lim_init+1,lim_init+k+1); 
}//Read the data and preliminarily process the databool check_data(){lim[m=1]=lim_init[1];for(int i=2;i<=k;i++)if (lim_init[i].pos==lim_init[i-1].pos){if (lim_init[i].val!=lim_init[i-1].val) return false;}else lim[++m]=lim_init[i];return true;
}//check if any possible solution is existint HPXXZYY(){read_data();if (!check_data())return printf("0\n");ans=ksm(v,(lim[1].pos-1)<<1);for(int i=2;i<=m;i++){int tmp=(ksm(v,(lim[i].pos-lim[i-1].pos)<<1)-1ll*(v-1)*ksm(v,lim[i].pos-lim[i-1].pos-1)%mod+mod)%mod;ans=1ll*ans*tmp%mod;}ans=1ll*ans*ksm(v,(n-lim[m].pos)<<1)%mod;return printf("%d\n",ans);
}int main(){T=read();while (T--) HPXXZYY();return 0;
}