[HNOI2008]越狱

退役后的第一篇题解

原题链接

某天数学课讲了一个非常类似的问题，我就思考了一下，感觉思维还没变弱

考虑容斥

首先全部的情况，对于\(n\)个屋子每个屋子有\(m\)种选择所以总的情况数为\(m^n\)

不满足条件的情况，即不会越狱的情况，首先第一个格子没有限制有\(m\)种选择，对于第二个格子不能和第一个相同故有\(m-1\)选择，第三个不能和第二个相同，但可以和第一个相同故有\(m-1\)种选择，以此类推不会发生越狱的情况有\(m\times (m-1)^{n-1}\)

所以答案为\(m^n - m \times (m-1)^{n-1}\)

快速幂，注意数据范围

#include <bits/stdc++.h>
#define LL long long
using namespace std;


const int p = 100003;
LL n , m ;


inline LL power( LL x , LL y )
{
    register LL ans = 1 ;
    for( ; y ; ) 
    {
        if( y & 1 ) ans = ans * x  % p; 
        x = x * x % p , y >>= 1 ; 
    }
    
    return ans ;
}


int main()
{
    cin >> m >> n;   
    printf( "%lld\n" ,  ( power( m , n ) + p - m % p  * power( m - 1 , n - 1 ) % p + p ) % p );
    return 0;
} 

[HNOI2008]越狱

原文：https://www.cnblogs.com/Mark-X/p/12096126.html