文档章节

ACM数学常用知识整理(持续更新ing)

o
 osc_1ee7cxmx
发布于 2018/08/07 09:38
字数 743
阅读 9
收藏 0
mul

精选30+云产品,助力企业轻松上云!>>>

1.最大公约数,最小公倍数

int gcd(int x,int y)
{
    int z=y;
    while(x%y!=0)
    {
        z=x%y;
        x=y;
        y=z;
    }
    return z;
}
int lcm(int x,int y)
{
    return x*y/gcd(x,y);
}
View Code

2.快速幂

 1 int qpow(int a,int b,int mod)//a^b
 2 {
 3     int t=1;
 4     while(b)
 5     {
 6         if(b&1)
 7         {
 8             t=(t*a)%mod;
 9             b--;
10         }
11         a=(a*a)%mod;
12         b>>=1;
13     }
14     return t;
View Code

>>矩阵快速幂 很久以前收集的模板,亲测可用

 1 struct Matrix
 2 {
 3     int m[3][3];
 4 };
 5 
 6 Matrix Mul(Matrix a,Matrix b)
 7 {
 8     Matrix c;
 9     memset(c.m,0,sizeof(c.m));
10     for(int i=0;i<3;i++)
11         for(int j=0;j<3;j++)
12             for(int k=0;k<3;k++)
13                 c.m[i][j] += ((a.m[i][k]*b.m[k][j])%SMod + SMod)%SMod;
14     return c;
15 }
16 
17 Matrix fastm(Matrix a,int n) 
18 {
19     Matrix res;
20     memset(res.m,0,sizeof(res.m));
21     res.m[0][0] = res.m[1][1] = res.m[2][2] = 1;
22     while(n)
23     {
24         if(n&1)
25             res = Mul(res,a);
26         n>>=1;
27         a = Mul(a,a);
28     }
29     return res;
30 }
31 
32 Matrix MPow(Matrix a,int n)  //第二种写法,慎用,易RE
33 {
34     if(n == 1)
35         return a;
36     Matrix res = fastm(a,n/2);
37     res = Mul(res,res);
38     if(n&1)
39         res = Mul(res,a);
40     return res;
41 }
View Code

另外一种

 1 struct Matrix
 2 {
 3     lll m[13][13];
 4     Matrix()
 5     {
 6         memset(m,0,sizeof(m));
 7         for(int i=1;i<=n+2;i++)
 8             m[i][i] = 1LL;
 9     }
10 };
11 
12 Matrix Mul(Matrix a,Matrix b)
13 {
14     Matrix res;
15     int i,j,k;
16     for(i=1;i<=n+2;i++)
17     {
18         for(j=1;j<=n+2;j++)
19         {
20             res.m[i][j] = 0;
21             for(k=1;k<=n+2;k++)
22                 res.m[i][j] = (res.m[i][j]+(a.m[i][k]*b.m[k][j])%SMod + SMod)%SMod;
23         }
24     }
25     return res;
26 }
27 
28 Matrix fastm(Matrix a,int b)
29 {
30     Matrix res;
31     while(b)
32     {
33         if(b&1)
34             res = Mul(res,a);
35         a = Mul(a,a);
36         b >>= 1;
37     }
38     return res;
39 }
View Code

对元素0较多的矩阵取快速幂时可在Mul函数中加一个小优化:

 

 1 Matrix Mul(Matrix a,Matrix b)
 2 {
 3     Matrix res;
 4     int i,j,k;
 5     memset(res.m,0,sizeof(res.m));
 6     for(k=1;k<=n+2;k++)
 7     {
 8         for(i=1;i<=n+2;i++)
 9         {
10             if(a.m[i][k])
11             {
12                 for(j=1;j<=n+2;j++)
13                     res.m[i][j] = (res.m[i][j]+(a.m[i][k]*b.m[k][j])%SMod + SMod)%SMod;
14             }
15         }
16     }
17     return res;
18 }
View Code

 

3.排列组合

 

 1 LL A(int n,int m)//n>=m
 2 {
 3     int ans=1;
 4     if(n<m)return 0;
 5     while(m--)
 6     {
 7         ans*=n;
 8         n--;
 9     }
10     return ans;
11 }
12 LL C(int n,int m)
13 {
14     if(n<m)return 0;
15     return A(n,m)/A(m,m);
16 }
View Code

 组合数性质:从这看到的:https://blog.csdn.net/litble/article/details/75913032

4.错排

D(n) = (n-1) [D(n-2) + D(n-1)](n物品全部错位的方案数)

D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].

记住公式就知道代码了

5.费马小定理: 假如p质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)。(如果a为整数,p为质数,a和p互质,则a的p-1次幂对p取模永远等于1)

 

上一篇: dataX json配置
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

OSChina 周一乱弹 —— 毛巾又怎么样?!我在乎的是大姐姐温柔的怀抱!

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《雨 因你而下,于你而止》- Seto 手机党少年们想听歌,请使劲儿戳(这里) @Dan...

小小编辑
23分钟前
29
1
MySQL 常用操作

1 创建/打开/删除数据库 create database db;create database db character set utf8mb4;use db;drop database db;alter database db character set utf8mb4; 2 修复表 mysqlcheck --a......

氷泠
27分钟前
13
0
Node.js中的module.exports与export - module.exports vs exports in Node.js

问题: I've found the following contract in a Node.js module: 我在Node.js模块中找到了以下合同: module.exports = exports = nano = function database_module(cfg) {...} I wonder ......

javail
33分钟前
13
0
如何防止单击按钮时对话框关闭 - How to prevent a dialog from closing when a button is clicked

问题: I have a dialog with EditText for input. 我有一个使用EditText输入的对话框。 When I click the "yes" button on dialog, it will validate the input and then close the dialog.......

富含淀粉
今天
17
0
访问者模式Visitor

一 概述 场景:通常来说,用于封装数据所用到的pojo类,其只包含get、set,对应的业务逻辑是在Service上完成的;但如果出现多个pojo类都共用一套逻辑时,则应该考虑将逻辑进行抽象,不同类型...

小明不觉小
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部