信息学奥赛一本通 1618：越狱 | 洛谷 P3197 [HNOI2008] 越狱
【题目链接】
ybt 1618：越狱
洛谷 P3197 [HNOI2008] 越狱
【题目考点】
1. 补集转化
当集合本身元素个数很难分析，但全集和补集都很容易求解时，可以先求出全集和补集的元素个数，二者相减就是所求集合元素的个数。
例：求从5个小球的排列中选出2个不相邻的小球的情况数。
5个小球中选出2个小球的总方案数是C 5 2 C_5^2C52，选出2个相邻小球的情况有4种，那么选出两个不相邻小球的方案数为总方案数减去5个小球中选出2个相邻小球的方案数，即C 5 2 − 4 = 6 C_5^2-4=6C52−4=6
2. 快速幂
3. 费马小定理
【解题思路】
该问题可以等价为：n nn个数值范围为[ 1 , m ] [1,m][1,m]的整数构成序列，求存在相邻两元素数值相等的序列的数量。
这样满足要求的序列很难求。可以考虑求其“补集”的情况数量，也就是该问题“反面”的情况。
先求出“全集”的情况数，即n nn个数值范围为[ 1 , m ] [1,m][1,m]的整数构成的序列的总数量。
第1步确定第1个元素的值，可以是[ 1 , m ] [1,m][1,m]中的整数，共m mm种情况。
第2步确定第2个元素的值，可以是[ 1 , m ] [1,m][1,m]中的整数，共m mm种情况。
…
第n nn步确定第n nn个元素的值，可以是[ 1 , m ] [1,m][1,m]中的整数，共m mm种情况。
根据乘法原理，n nn个数值范围为[ 1 , m ] [1,m][1,m]的整数构成的序列的总数量为m n m^nmn。
接下来求“补集”的情况数。考虑不满足“存在相邻两元素数值相等”的序列，即相邻元素数值都不相等的序列。
第1步确定第1个元素的值，可以是[ 1 , m ] [1,m][1,m]中的整数，共m mm种情况，假设选定的数值为a 1 a_1a1
第2步确定第2个元素的值，可以是[ 1 , m ] [1,m][1,m]中的不等于a 1 a_1a1的整数，共m − 1 m-1m−1种情况，假设选定的数值为a 2 a_2a2
第3步确定第3个元素的值，可以是[ 1 , m ] [1,m][1,m]中的不等于a 2 a_2a2的整数，共m − 1 m-1m−1种情况，假设选定的数值为a 3 a_3a3
…
第n nn步确定第n nn个元素的值，可以是[ 1 , m ] [1,m][1,m]中的不等于a n − 1 a_{n-1}an−1的整数，共m − 1 m-1m−1种情况，假设选定的数值为a n a_nan
因此相邻元素数值都不想等的序列数量为m ⋅ ( m − 1 ) n − 1 m\cdot(m-1)^{n-1}m⋅(m−1)n−1
n nn个数值范围为[ 1 , m ] [1,m][1,m]的整数构成序列中，存在相邻两元素数值相等的序列的数量，为总序列数量减去相邻元素数值都不想等的序列的数量，即m n − m ⋅ ( m − 1 ) n − 1 m^n-m\cdot(m-1)^{n-1}mn−m⋅(m−1)n−1。
设P = 100003 P=100003P=100003，可以通过质数判定方法确定P PP为质数。
因此所求结果为：
( m n − m ⋅ ( m − 1 ) n − 1 ) m o d P = ( m n m o d P − ( m ⋅ ( m − 1 ) n − 1 ) m o d P ) m o d P (m^n-m\cdot(m-1)^{n-1}) \bmod P\\ =(m^n \bmod P-(m\cdot(m-1)^{n-1})\bmod P)\bmod P(mn−m⋅(m−1)n−1)modP=(mnmodP−(m⋅(m−1)n−1)modP)modP
可以直接使用快速幂求解。
也可以使用费马小定理降幂求解。根据费马小定理，当p pp为质数时：a b m o d p = ( a m o d p ) b m o d ( p − 1 ) m o d p a^b\bmod p = (a\bmod p)^{b\bmod (p-1)}\bmod pabmodp=(amodp)bmod(p−1)modp
所以：( m n m o d P − ( m ⋅ ( m − 1 ) n − 1 ) m o d P ) m o d P = ( ( m m o d P ) n m o d ( P − 1 ) − ( m m o d P ) ( ( m − 1 ) m o d P ) ( n − 1 ) m o d ( P − 1 ) ) m o d P (m^n \bmod P-(m\cdot(m-1)^{n-1})\bmod P)\bmod P\\ =((m\bmod P)^{n\bmod (P-1)}-(m\bmod P)((m-1)\bmod P)^{(n-1)\bmod (P-1)})\bmod P(mnmodP−(m⋅(m−1)n−1)modP)modP=((mmodP)nmod(P−1)−(mmodP)((m−1)modP)(n−1)mod(P−1))modP
注意：两项相减结果可能为负，所以最后一步必须进行数学取模。
【题解代码】
解法1：直接使用快速幂求解
#include<bits/stdc++.h>usingnamespacestd;#defineMOD(a,b)(((a)%(b)+(b))%(b))constintP=100003;typedeflonglongLL;LLfastPow(LL a,LL b,LL m){LL r=1;while(b>0){if(b%2==1)r=r*a%m;a=a*a%m;b/=2;}returnr;}intmain(){LL m,n;cin>>m>>n;cout<<MOD(fastPow(m,n,P)-m*fastPow(m-1,n-1,P),P);return0;}解法2：使用费马小定理降幂求解
#include<bits/stdc++.h>usingnamespacestd;#defineMOD(a,b)(((a)%(b)+(b))%(b))constintP=100003;typedeflonglongLL;LLfastPow(LL a,LL b,LL m){LL r=1;while(b>0){if(b%2==1)r=r*a%m;a=a*a%m;b/=2;}returnr;}intmain(){LL m,n;cin>>m>>n;cout<<MOD(fastPow(m%P,n%(P-1),P)-m*fastPow((m-1)%P,(n-1)%(P-1),P),P);return0;}