BZOJ1008 [HNOI2008]越狱 (快速幂，组合)

2024-10-20 01:29:16

题目大意

求\(m\)种数字组成的长度为\(n\)的序列的种数，序列中至少有一段连续的数字

分析

用可重排列的种数减去，相邻数字互不相同的序列种数

考虑相邻互不相同，第一个元素有\(m\)种可能，后面每个元素不能和它左边的那个数一样，有\(m-1\)种可能

即$$m^n - m(m-1)^{n-1}$$

代码

#include<iostream>

#include<cmath>

#include<cstdio>

#define LL long long 

using namespace std;

const LL p = 100003;

LL pw(LL a,LL b){

   LL t = 1;

   for (;b;b >>= 1) {

       if (b & 1) t = t * a % p;

	   a = a % p * a % p;

   }

   return t;

}

int main(){

	LL n,m;

	scanf("%lld%lld",&m,&n);

	printf("%lld\n",(p + pw(m,n) - m  * pw(m - 1,n - 1) % p) % p);

	return 0;

}

最新文章

热门文章