2. it
  3. 「HNOI2008」「LuoguP3197」越狱（数论

「HNOI2008」「LuoguP3197」越狱（数论

mac2022-06-30  22

题目描述

原题来自：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$。

1 /* 2 qwerta 3 P3197 [HNOI2008]越狱 Accepted 4 100 5 代码 C++，0.38KB 6 提交时间 2018-10-23 17:02:41 7 耗时/内存 25ms, 804KB 8 */ 9 #include<iostream> 10 #include<cstdio> 11 using namespace std; 12 #define LL long long 13 const int mod=100003; 14 LL pown(LL q,LL w) 15 { 16 LL ans=1,base=q; 17 LL k=w; 18 while(k) 19 { 20 if(k&1) 21 ans=ans*base%mod; 22 base=base*base%mod; 23 k>>=1; 24 } 25 return ans; 26 } 27 int main() 28 { 29 int m; 30 cin>>m; 31 LL n; 32 cin>>n; 33 LL res=m*pown(m-1,n-1)%mod; 34 LL al=pown(m,n)%mod; 35 LL ans=(al-res+mod)%mod; 36 cout<<ans; 37 return 0; 38 }

 

转载于:https://www.cnblogs.com/qwerta/p/9839867.html

相关资源：JAVA上百实例源码以及开源项目
最新回复(0)