当前位置: 首页> 汽车> 新车 > 深圳网站制作公司售后_电子工程网校_搜索引擎广告案例_网络营销的好处和优势

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

时间:2025/7/11 7:33:43来源:https://blog.csdn.net/ZHUYINGYE_123456/article/details/144251039 浏览次数: 0次
深圳网站制作公司售后_电子工程网校_搜索引擎广告案例_网络营销的好处和优势

[Problem Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription]

在这里插入图片描述

[Analysis] \color{blue}{\texttt{[Analysis]}} [Analysis]

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

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

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

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

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

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

形式化地说,就是:

a λ = d x , b λ ∈ [ 1 , v ] a_{\lambda}=d_{x},b_{\lambda} \in [1,v] aλ=dx,bλ[1,v]

a λ + 1 = b λ , b λ + 1 ∈ [ 1 , v ] a_{\lambda+1}=b_{\lambda},b_{\lambda+1} \in [1,v] aλ+1=bλ,bλ+1[1,v]

a λ + 2 = b λ + 1 , b λ + 2 ∈ [ 1 , v ] a_{\lambda+2}=b_{\lambda+1},b_{\lambda+2} \in [1,v] aλ+2=bλ+1,bλ+2[1,v]

⋯ \cdots

a μ = b μ − 1 , b μ ∈ [ 1 , v ] , b μ ≠ d y a_{\mu}=b_{\mu-1},b_{\mu} \in [1,v],b_{\mu} \not = d_{y} aμ=bμ1,bμ[1,v],bμ=dy

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

于是在区间 [ x , y ] [x,y] [x,y] 中合法的方案数为 v 2 ( y − x ) − ( v − 1 ) × v y − x − 1 v^{2(y-x)}-(v-1) \times v^{y-x-1} v2(yx)(v1)×vyx1

分段累计即可。

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

[Code] \color{blue}{\text{[Code]}} [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;
}
关键字:深圳网站制作公司售后_电子工程网校_搜索引擎广告案例_网络营销的好处和优势

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: