P3197 [HNOI2008] 越狱

题目传送门

题面

[HNOI2008] 越狱

题目描述

监狱有 $n$ 个房间，每个房间关押一个犯人，有 $m$ 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对 $100,003$ 取模。

输入格式

输入只有一行两个整数，分别代表宗教数 $m$ 和房间数 $n$。

输出格式

输出一行一个整数代表答案。

样例 #1

样例输入 #1

2 3

样例输出 #1

6

提示

样例输入输出 1 解释

状态编号	1 号房间	2 号房间	3 号房间
1	信仰 1	信仰 1	信仰 1
2	信仰 1	信仰 1	信仰 2
3	信仰 1	信仰 2	信仰 2
4	信仰 2	信仰 1	信仰 1
5	信仰 2	信仰 2	信仰 2
6	信仰 2	信仰 2	信仰 1

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le m\le 10^8$，$1\le n\le 10^{12}$。

思路

先正常看，题目难度普及/提高，所以有很大的思维成分在里面。
然后的话这是标签：

明显这是一道排列组合题目。
先考虑会越狱情况下的各种情况
这是样例1的

状态编号	1 号房间	2 号房间	3 号房间
1	信仰 1	信仰 1	信仰 1
2	信仰 1	信仰 1	信仰 2
3	信仰 1	信仰 2	信仰 2
4	信仰 2	信仰 1	信仰 1
5	信仰 2	信仰 2	信仰 2
6	信仰 2	信仰 2	信仰 1

很明显，从2个一样信仰的相邻一直到n个一样的信仰相邻都有多种可能，所以从这个方向考虑会很复杂。
那么可以换一种思路，从逆向来想，因为只有两种情况，要么越狱，要么不越狱，所以可以理解为$$越狱的情况=所有情况-不越狱的情况$$
那么考虑一下不越狱的情况。
有m中信仰的情况下，具体可以这样分配：

1 号房间	2 号房间	3 号房间	…	3n号房间
m种信仰	m-1种信仰	m-1种信仰	m-1种信仰	m-1种信仰

因为为了不和上一个房间的宗教相同，所以剩下了除上一个房间以外m-1种信仰可选，然而第一间左边没有房间可以有m种选择。
因此我们可以把答案弄出来了
$$ans=n^m-m\ast (n-1{)}^{m-1}$$
接着看数据范围，保证 $1\le m\le 10^8$，$1\le n\le 10^{12}$，所以如果用O(n)的时间复杂度会过不了($10^8$有的判题机好似可以过)
所以要用快速幂，原理就是倍增思想，时间复杂度降低到了$log(n)$

虽然c++本身有快速幂函数pow，不过由于涉及取模，所以需要手写一个。

最后提交上去就会发现有的点WA了，由于这里面取模运算的特性，所以有可能会出现$n^m$取模完以后比后面那一坨还小，这时候我们就应该加上一个模数就可以了

$code$

#include<bits/stdc++.h>
using namespace std;
//#define ll long long防伪认证
#define ld long double
#define FOR(x,a,b,c) for(int x=a;x<=b;x+=c)
#define MFOR(x,a,b,c) for(int x=a;x>=b;x-=c)
#define MPFOR(x,a,b,c) for(int x=a;a<=b;x*=c)
const int N3=1e3+10;
const int N=1e6+10;
const long double esp=1e-8;
bool f[N];
/*/防伪认证
map<ll,int> a;
queue<int> a;
stack<int> a;
priority_queue<int> a;
vector<int> a;
set<int> a;
::iterator it
unordered
/*/
int gcd(int a,int b){int c=a%b;while(a%b!=0){a=b;b=c;c=a%b;}return b;
}
int lcm(int x,int y){return (x*y)/gcd(x,y);
}
void p(int n){f[1]=1;f[0]=1;for(int i=2;i*i<=n;i++){if(f[i]) continue;for(int j=i*i;j<=n;j+=i){f[j]=1;}}
}
ll qpow(ll x,ll y,ll md){//快速幂ll ans=1;while(y){//相当于给他求二进制if(y&1){ans*=x;ans%=md;}x*=x;//倍增思想x%=md;y>>=1;}return ans;
}
ll n,m;
ll ans=1;
int main(){freopen(".in","r",stdin);freopen(".out","w",stdout);ios::sync_with_stdio(false);cin>>m>>n;ans=((qpow(m,n,100003))-m*qpow(m-1,n-1,100003)%100003)%100003;//公式计算if(ans<0) ans+=100003;//特殊情况cout<<ans;fclose(stdin);fclose(stdout);return 0;
}
/*/
思路区
/*/

不要复制以后直接提交，不会AC，会编译错误！！！