越狱

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 664 字

n个房间m种宗教，求相邻房间宗教相同的状态数

一本通
练习

正文

/*
原题：越狱
题意：n 个房间 m 种宗教，求相邻房间宗教相同的状态数 mod 100003。
思路：总状态 m^n，不越狱状态 m*(m-1)^(n-1)，答案 = (m^n - m*(m-1)^(n-1)) mod 100003，用快速幂。
复杂度：O(log n) 时间 / O(1) 空间
易错点：n 可达 1e12 用 long long；相减结果可能为负需加模再取模；m 先取模。
*/
#include <bits/stdc++.h>
using namespace std;
const long long MOD=100003;
long long qpow(long long a,long long b){
    long long res=1%MOD;
    a%=MOD;
    while(b){
        if(b&1){ res=res*a%MOD; }
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
int main(){
    long long m,n;
    cin>>m>>n;
    long long total=qpow(m,n);
    long long safe=m%MOD*qpow((m-1)%MOD,n-1)%MOD;
    long long ans=(total-safe+MOD)%MOD;
    cout<<ans<<'\n';
    return 0;
}

越狱

正文

一本通·提高篇的其它内容