「HNOI2008」「LuoguP3197」越狱（数论

题目描述

原题来自：HNOI 2008

监狱有连续编号为 111 到 nnn 的 nnn 个房间，每个房间关押一个犯人。有 mmm 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。

输入格式

输入两个整数 mmm 和 nnn。

输出格式

可能越狱的状态数，对 100003100003100003 取余。

样例

样例输入

2 3

样例输出

6

样例说明

所有可能的 666 种状态为：{0,0,0},{0,0,1},{0,1,1},{1,0,0},{1,1,0},{1,1,1}\{0,0,0\},\{0,0,1\},\{0,1,1\},\{1,0,0\},\{1,1,0\},\{1,1,1\}{0,0,0},{0,0,1},{0,1,1},{1,0,0},{1,1,0},{1,1,1}。

数据范围与提示

对于全部数据，1≤m≤108,1≤n≤10121\le m\le 10^8,1\le n\le 10^{12}1≤m≤10​8​​,1≤n≤10​12​​。

题解

这还能绿？！

正难则反，考虑不能越狱的情况，转化成线上的地图染色问题，方案为$m*\underbrace{(m-1)*(m-1)*...*(m-1)}_{(n-1)个}$，设为$res$。

然后所有可能为$m^n$。

所以答案就是$m^n-res$。

 /*

  qwerta

 P3197 [HNOI2008]越狱 Accepted

 100

 代码 C++，0.38KB

 提交时间 2018-10-23 17:02:41

 耗时/内存 25ms, 804KB

 */

 #include<iostream>

 #include<cstdio>

 using namespace std;

 #define LL long long

 const int mod=;

 LL pown(LL q,LL w)

 {

     LL ans=,base=q;

     LL k=w;

     while(k)

     {

         if(k&)

         ans=ans*base%mod;

         base=base*base%mod;

         k>>=;

     }

     return ans;

 }

 int main()

 {

     int m;

     cin>>m;

     LL n;

     cin>>n;

     LL res=m*pown(m-,n-)%mod;

     LL al=pown(m,n)%mod;

     LL ans=(al-res+mod)%mod;

     cout<<ans;

     return ;

 }