P3197 [HNOI2008] 越狱——题解

解题思路

所有分配共有 $m^n$ 种。计算补集：没有任何相邻房间信仰相同。第一个房间有 $m$ 种选择，后面每个房间都不能与前一个相同，各有 $m-1$ 种，因此安全状态为 $m(m-1)^{n-1}$。两者相减并取模，幂用快速幂。

正确性说明

全部状态被划分为“至少一对相邻相同”和“所有相邻均不同”两类，互斥且完备。后者按从左到右乘法原理计数为 $m(m-1)^{n-1}$，故相减得到目标。

复杂度分析

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

易错点

相减后要加上模数再取模，避免输出负数；当 $n=1$ 时快速幂指数为 0，答案自然为 0。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
const long long MOD=100003;
long long qpow(long long a,long long b){long long r=1;a%=MOD;while(b){if(b&1)r=r*a%MOD;a=a*a%MOD;b>>=1;}return r;}
int main(){
    long long m,n;cin>>m>>n;
    long long all=qpow(m,n);
    long long safe=m%MOD*qpow(m-1,n-1)%MOD;
    cout<<(all-safe+MOD)%MOD<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; const long long MOD=100003; long long qpow(long long a,long long b){long long r=1;a%=MOD;while(b){if(b&1)r=ra%MOD;a=aa%MOD;b>>=1;}return r;} int main(){ long long m,n;cin>>m>>n; long long all=qpow(m,n); long long safe=m%MOD*qpow(m-1,n-1)%MOD; cout<<(all-safe+MOD)%MOD<<'\n';return 0; }