HYSBZ - 1008越狱（大数幂减法取模）

2019-04-13 14:21发布

站内文章 / 模拟电子
13808 0 1531

1008: [HNOI2008]越狱

Time Limit: 1 Sec  Memory Limit: 162 MB
Submit: 12198  Solved: 5256
[Submit][Status][Discuss]

Description

　　监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果
相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱

Input

　　输入两个整数M，N.1<=M<=10^8,1<=N<=10^12

Output

　　可能越狱的状态数，模100003取余

Sample Input

2 3

Sample Output

6

HINT

  　　6种状态为(000)(001)(011)(100)(110)(111)   总共有m^n种情况，不越狱的情况有m*(m-1)^(n-1)种情况，所以不越狱的情况有 m^n-m*(m-1)^(n-1)；   #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int mod = 1e5+3; ll quick_mod( ll a, ll b)//快速幂 { ll ans = 1 ; a %= mod; while ( b ) { if ( b & 1 ) { ans = ans * a % mod; b--; } b >>= 1; a = a * a % mod; } return ans; } int main() { ll m,n; cin >> m >> n; ll ans = (quick_mod(m%mod,n)%mod - (m%mod*(quick_mod((m-1)%mod,(n-1))))%mod)%mod; //a^b%mod = ((a%mod)^b)%mod,（注意，b不对mod取模） if(ans<0) ans+=mod;//取模以后可能前面的小于后面的，结果可能是负数，所以要加一个mod cout << ans << endl; return 0; }  

热门文章