2022.1.29 训练日记 2 AcWing 1290. 越狱

题目链接:越狱


题目分析:
0.快速幂+组合数+容斥原理(补集思想)
1.本题可以采用容斥原理补集的思想。
考虑 n 个犯人,m种宗教,如何安排不会导致犯罪。
第一个位置可以有 m 个选择,则与第一个相邻的第二个位置就只有 m−1种选择。考虑第 i个位置,则为了不和他左侧的 i-1 位置发生冲突,一共有 m−1种选择。
因此不会导致犯罪的方案是: m⋅(m−1)^n-1
则会导致犯罪的方案是:m^n−m⋅(m−1)^n−1

code:
#include <iostream>
#include <cstring>
#include <algorithm>

typedef long long ll;

using namespace std;

const int mod = 100003;
//快速幂,b会超int 范围。
int qmi(int a, ll b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (ll) res * a % mod;
        a = (ll) a * a % mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    ll n, m;
    cin >> m >> n;//注意看题目 不要读反
    
    cout << (qmi(m, n) - (ll)m * qmi(m - 1, n - 1) % mod + mod) % mod << endl;
    return 0;
}

总结:
1.取模答案会为负数的时候。解决方法:加一个mod 再和mod取余。
 1.1 例如模数是 10,那么 11 - 8 取模以后就是 1 - 8 是负数
2.容斥原理:

2022.1.29 训练日记 2 AcWing 1290. 越狱
2022.1.29 训练日记 2 AcWing 1290. 越狱

上一篇:P4247 [清华集训2012]序列操作


下一篇:扩展欧几里得算法