[HNOI2008]越狱题解

[陶荣杰1 (Chtholly)]

[HNOI2008]越狱题解

• 题目描述

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

  答案对 100,003 取模。

  • 思路分析

    乍一看好像很难直接求出方案数，所以正难则反，我们不妨计算不满足条件的方案数，用总方案数减去便是答案。

    第一个人有 m 种选择，与他相邻的第二个人便又 m-1 种选择,相邻的第三个人便也有 m-1 种选择，以此类推…所以答案便是：

    m^n-m*(m-1)^{n-1}

    附上代码:

    m,n=map(int,input().split())
    ans=(pow(m,n)-m*pow(m-1,n-1))%100003 
    print(ans)
    

我们充分发扬Python智慧！

[金杭东]

@陶荣杰1

我们充分发扬Python智慧！

请用 c++ 谢谢
请用 c++ 谢谢
请用 c++ 谢谢

[陶荣杰1 (Chtholly)]

大哥，这就三行代码用个锤子c++

[金杭东]

我c++可以两行

[陶荣杰1 (Chtholly)]

那你写去吧

[程诺 (【语法】顺序结构)]

[金杭东]

写好了

#include<bits/stdc++.h>
using namespace std;const int Mod=1e5+3;long long n,m;long long qpow(long long x,long long y){if(y==0) return 1;if(y==1) return x%Mod;long long t=qpow(x,y/2);if(y%2) return (t*t%Mod*(x%Mod))%Mod;return (t*t)%Mod;}int main(){cin>>m>>n;cout<<((qpow(m,n)-(m*qpow(m-1,n-1))%Mod)%Mod+Mod)%Mod;return 0;}

[zhenghaoren2024 (我永远喜欢数据结构)]

。。。

[zhenghaoren2024 (我永远喜欢数据结构)]

极致压行

[zhenghaoren2024 (我永远喜欢数据结构)]

@陈洪森

#include<bits/stdc++.h>using namespace std;const int Mod=1e5+3;long long n,m;long long qpow(long long x,long long y){if(y==0) return 1;if(y==1) return x%Mod;long long t=qpow(x,y/2);if(y%2) return (t*t%Mod*(x%Mod))%Mod;return (t*t)%Mod;}int main(){cin>>m>>n;cout<<((qpow(m,n)-(m*qpow(m-1,n-1))%Mod)%Mod+Mod)%Mod;return 0;}

过不了编译

[zhenghaoren2024 (我永远喜欢数据结构)]

@陈洪森

#include<bits/stdc++.h> 
















using namespace std;const int Mod=1e5+3;long long n,m;long long qpow(lo

这是一行吗

[李政烨 (漂亮奶奶)]

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

[崩坏星穹铁道]

@陶荣杰1

m,n=map(int,input().split())
ans=(pow(m,n)-m*pow(m-1,n-1))%100003 
print(ans)

python会TLE

[崩坏星穹铁道]

快速幂它不香吗？

[陶荣杰1 (Chtholly)]

那是洛谷会tle，xyd直接a

[崩坏星穹铁道]

真不知道有啥智慧,xyd太水了