[模板] 模意义下的高斯消元

数学

模板题Det(A) mod M

你可以:

写高精度分数类最后取模?可以,就是运算量太大了

分解模数,模数是质数的时候除法运算保证可以变成乘乘法逆元,最后结果用中国剩余定理合并?好

有一种更巧妙的方法,见国家集训队2009年论文《欧几里得算法的应用》

应用其中的方法,把取模变成行列式初等变换。

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <algorithm>
using namespace std
typedef long long LL
LL A[2
阅读全文 >>

发表于 2017.05.26

[题解] BZOJ1008&HNOI2008 越狱

数学

题目

超级水,用M个格子给N个格子染色,要求存在至少存在两个相邻的格子颜色相同的方案数,我们反过来,求任意相邻两个格子颜色不相同的方案数,用总方案数减去即可。

设F(n) 为给前N个格子染色,任意相邻两个格子颜色不同的方案数,的方案数,我们有:

因为对于第n个格子来说,为了和第(n-1)个格子颜色不同,有(M-1)种选择。求通项得到

最后的答案就是

#include <cstdio>
using namespace std
typedef long long LL
const int MOD = 100003;
LL pow_mod(LL a, LL x){
阅读全文 >>

发表于 2017.05.21

近期博客

博客更新日志:

修正了一个搜索文章的naive的bug
博客侧栏近期评论支持点击进入对应文章,并且直接到评论 2016.09.01
添加"打赏"页面
更改首页和博客文章页布局
... ... ... ...