題目描述

監獄有連續編號為?1…N1…N?的?NN?個房間，每個房間關押一個犯人，有?MM?種宗教，每個犯人可能信仰其中一種。如果相鄰房間的犯人的宗教相同，就可能發生越獄，求有多少種狀態可能發生越獄。

輸入輸出格式

輸入格式：

?

輸入兩個整數?$M，N$

?

輸出格式：

?

可能越獄的狀態數，模?100003100003?取余

?

輸入輸出樣例

輸入樣例#1：?復制 2 3 輸出樣例#1：?復制 6

說明

6種狀態為(000)(001)(011)(100)(110)(111)

1 \le M \le 10^81≤M≤108
1 \le N \le 10^{12}1≤N≤1012

?

很zz的數數題。

發現直接數不好數，那就容斥一下吧，。

所有的情況是$M^N$，兩兩不能相鄰，那么第一個可以選$M$個，第二個可以選$M - 1$個，以此類推都能選$M - 1$個

因此答案為$M^N - M * (N - 1)^{M - 1}$

?

#include<cstdio> #include<algorithm> #include<cmath> #include<map> #define int long long using namespace std; const int MAXN = 4 * 1e5 + 10, mod = 100003; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } int M, N; int fastpow(int a, int p) {int base = 1;while(p) {if(p & 1) base = (base % mod * a % mod) % mod;a = (a % mod * a % mod) % mod; p >>= 1;}return base % mod; } main() {M = read(); N = read();//M %= mod; N %= mod;printf("%lld", (fastpow(M, N) - (M % mod) * (fastpow(M - 1, N - 1)) % mod + mod) % mod); }

?

轉載于:https://www.cnblogs.com/zwfymqz/p/9290828.html

總結

以上是生活随笔為你收集整理的BZOJ1008: [HNOI2008]越狱(组合数)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。