本文共 1163 字，大约阅读时间需要 3 分钟。

Hmz 的女装

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 190 Accepted Submission(s): 92

Problem Description

Hmz为了女装，想给自己做一个长度为n的花环。现在有k种花可以选取，且花环上相邻花的种类不能相同。Hmz想知道，如果他要求第l朵花和第r朵花颜色相同，做花环的方案数是多少。这个答案可能会很大，你只要输出答案对10^9+7取模的结果即可。

Input

第一行三个整数n,m,k(1≤n≤100000,1≤m≤100000,1≤k≤100000)接下来m行，每行两个整数l,r，表示要求第l朵花和第r朵花颜色相同。保证l≠r且 |(r-l) mod n| ≠1.

Output

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

Sample Input

8 3 2

1 42 61 38 3 31 42 61 3

Sample Output

0

2260108132

题意

分析

这道题蛮难想的，也许是我做过的题太少

我们可以观察到两个相同点将环分成两段，这两段的花分配的种数互不影响（请仔细思考）。对于其中任意一段，我们考虑从一端开始扩展，我们设置d[i][0]为长度i（都不包含固定端），第i朵花与固定端相同的方案数。d[i][1]为长度i，第i朵花与固定端颜色相同的方案数推出dp[i][0]=dp[i-1][1];dp[i][1]=dp[i-1][1](k-2)+dp[i][0](k-1)由于要与固定端不同，只要最后去dp[len][1]即可，最后答案为dp[len1][1]dp[len2][1]k即可，k为固定端颜色可取种数推荐相似blog

trick

1.注意取模

代码

#include 
   
    using namespace std;#define ll long long#define F(i,a,b) for(int i=a;i<=b;++i)#define R(i,a,b) for(int i=a;i
    
     r) swap(l,r);            ll ans;            int len1=r-l-1,len2=(n-r+l-1);            ans=k*dp[len1][1]%mod*dp[len2][1]%mod;            printf("%I64d\n",ans%mod);        }    }    return 0;}