即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Hmz 的女装 详细题解

编程语言 qq_33417653 10℃ 0评论
本文目录
[隐藏]

1.问题 F: Hmz 的女装

时间限制: 2 秒  内存限制: 128 MB


提交: 109  解决: 30


提交 状态 

1.1.1.题目描述

Hmz为了女装,想给自己做一个长度为n的花环。现在有k种花可以选取,且花环上相邻花的种类不能相同。


Hmz想知道,如果他要求第l朵花和第r朵花颜色相同,做花环的方案数是多少。这个答案可能会很大,你只要输出答案对10^9+7取模的结果即可。

1.1.2.输入

第一行三个整数n,m,k(1≤n≤100000,1≤m≤100000,1≤k≤100000)


接下来m行,每行两个整数l,r,表示要求第l朵花和第r朵花颜色相同。保证lr且 |(rlmod n| ≠1.

1.1.3.输出

输出m行。对于每一个询问输出一个整数,表示做花环的方案数对10^9+7取模的结果。

1.1.4.样例输入

8 3 21 42 61 38 3 31 42 61 3

1.1.5.样例输出

02260108132


这道题是我在比赛之后想出来的,比赛时估计脑子比较热,冷静下来就想出来了。。。

此题可用DP解决,需要维护两个状态:DP1【i】表示两端花相同时的种类,和DP2[i]表示两端花不同时的种类(下标i代表的是两端花中间的花数),理解了题目意思,状态转移方程就很容易出来,要分两端相同和不同分别讨论。


下面举例说明递推关系:以k = 3(花种数) 为例 (先不考虑环状,只考虑线状)

要求DP1【5】的话  即要求形如A _ _ _ _ _ A 可能的种数(A代表颜色 _代表中间花)

只需要求Dp2【4】即形如 X _ _ _ _ A的的可能种数(X代表除A外的其他颜色, 此处X代表B、C 两者是完全等价的)再乘上k-1,即有DP1[i]= (k-1)*DP2[i-1] % mod;

那么DP2【4】怎么求呢,这时需要分情况讨论  (因为X以外的颜色可能有A!!这是关键!!)如果X右边的 花颜色为A 其值为DP1【3】,如果不为A,则为除A与X之外的,即有k-2 种(这个可能有点绕。。)既有DP2[i] = (DP1[i-1] + (k-2)*DP2[i-1] ) % mod;

初始状态如何确定? DP1【0】肯定为0(不能有相邻颜色相同的情况),DP2【0】为1(就XA 这一种)

最后输出k* DP1[p1]*DP1[p2] 即可 (为什么乘K,我一开始是用A举例的,但这个A可以是任意颜色)(p1 和 p2 分别表示题中两相同颜色花 之间的花个数 有两个方向)


另外,此题需要注意两个地方(坑了我好久的地方,萌新注意,大神可跳过):

题中没有说l 和r 的大小关系,如果直接r-l会越界,可以加一个预处理 ,将r换为大的,这样之后处理起来方便一些。

还有,最后输出的时候!! k* DP1[p1]*DP1[p2] % mod  有没有这么写的?有没有WA一脸蒙蔽的?大数相乘,一定要分部mod!!!这题这就设了个坑 如果没分部mod 就会爆long long。


终于AC代码。。。

#include
using namespace std;

#define ll long long 
const int maxn = 100010;
const int mod = 1e9 + 7;
ll int DP1[maxn];
ll int DP2[maxn];

int main(){
 int i,n,m,k,l,r,p1,p2;
 while(cin>>n>>m>>k){
  DP1[0] = 0;
  DP2[0] = 1;
  for(i=1; i<=n; i++){
   DP1[i] = (k-1)*DP2[i-1] % mod;
   DP2[i] = (DP1[i-1] + (k-2)*DP2[i-1] ) % mod;
  }
  while(m--){
   cin>>l>>r;
   if(r < l)swap(l, r);
   p1 = (r-l) % n - 1;
   p2 = n - 2 - p1;
   cout<<(k* (DP1[p1]*DP1[p2] % mod) ) % mod<





转载请注明:CodingBlog » Hmz 的女装 详细题解

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情