首页 > 学术百科

整理一些ACM基础数学算法模板

轻纺城整理⼀些ACM基础数学算法模板ACM训练整理的⼀些内容，，不知道放哪就丢这吧

欧拉函数模板

int r[] = new int [MAXN];

r[1] = 1;

for(int i = 2; i < MAXN; i++)

r[i] = i;

for(int i = 2; i < MAXN; i++)

if(r[i] == i)

for(int j = i; j < MAXN; j += i)

r[j] = r[j] / i * (i - 1);

快速幂模板 x^n

static long pow(long x,long n)

{人教出版社

long res = 1;

while(n>0)

{

if(n%2==1)

res = res*x%MOD;

x = x*x%MOD;

n/=2;

}

return res;

}

弗洛伊德扩展欧⼏⾥得算法模板

public static int extendgcd(int a,int b){

if(b==0){

x=1;

y=0;

return a;

}

int d=extendgcd(b,a%b);

int temp=x;

x=y;

y = temp-a/b*x;

return d;

}

求组合数的预处理模板对1000000007取余

static void PreWork()

{

for (int i=0;i<=1000;i++)

C[i][0]=1;

for (int i=1;i<=1000;i++)

for (int j=1;j<=1000;j++)

C[i][j]=(C[i-1][j]+C[i-1][j-1])%INF;

}

for(int i = 0;i<m;i++)

a[i] = in.nextInt(); 　// 除数，不⼀定互质

for(int i = 0;i<m;i++)

b[i] = in.nextInt(); //余数

int m1 = a[0],r1 = b[0],m2,r2;

int flag = 0;

for(int i=1;i<m;i++)

{

m2=a[i];王士伟

r2=b[i];

int c=r2-r1;

int d = extendgcd(m1,m2);//d=gcd(m1,m2);x*m1+y*m2=d;

if(c%d!=0)

{

flag =1;

break;

}

int t=m2/d;

x=(c/d*x%t+t)%t;

r1=m1*x+r1;

m1=m1*m2/d;

}

r1 为最⼩整数解 m1*i+r1 (i = 0,) 都是满⾜条件的解

除法取模 (费马⼩定理)

求 a / b = x (mod M)

只要 M 是⼀个素数，⽽且 b 不是 M 的倍数，就可以⽤⼀个逆元整数 b’，通过 a / b = a * b' (mod M)，来以乘换除。费马⼩定理说，对于素数 M 任意不是 M 的倍数的 b，都有：

b ^ (M-1) = 1 (mod M)

于是可以拆成：

b * b ^ (M-2) = 1 (mod M)

于是：

a /

b = a / b * (b * b ^ (M-2)) = a * (b ^ (M-2)) (mod M)

也就是说我们要求的逆元就是 b ^ (M-2) (mod M)求解fibonacci数列矩阵快速幂对10000取模

import java.util.Scanner;

public class Main {

2010年1月3日

private static final int MOD = 10000;

private static Node base;

private static Node ans;

public static void main(String[] args) {

base = new Node();

ans = new Node();

base.m = new int [2][2];

ans.m = new int [2][2];

Scanner in = new Scanner (System.in);

while(in.hasNext())

{

浪迹智能代理

int n = in.nextInt();

if(n==-1)

break;

System.out.println(fast_mod(n));

}

static int fast_mod(int n) // 求矩阵 base 的 n 次幂

{

base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;

base.m[1][1] = 0;

ans.m[0][0] = ans.m[1][1] = 1; // ans 初始化为单位矩阵

ans.m[0][1] = ans.m[1][0] = 0;

while(n!=0)

{

if(n % 2 == 1) //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后⽤ ans = tmp * t ans = multi(ans, base);

base = multi(base, base);

n >>= 1;

}

return ans.m[0][1];

}

static Node multi(Node a, Node b)//定义矩阵乘法

{

Node tmp = new Node();

tmp.m = new int [2][2];

for(int i = 0; i < 2; ++i)

{

for(int j = 0; j < 2; ++j)

{

tmp.m[i][j] = 0;

for(int k = 0; k < 2; ++k)

tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;

}

return tmp;

}

static class Node{

int m[][];

}

斯特林数（划分集合的⽅法数）

static void init()

{

s[1][1]=1;

for(int i=2; i<=1000; i++)

{

for(int j=1; j<=i; j++)

{

s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%INF; }

}

待补充。。。

本文发布于:2024-09-21 16:30:33，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/471067.html

上一篇：第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛前十题（能力有限）

下一篇：顶级会议及期刊

标签：模板整理算法矩阵逆元素数训练基础

留言与评论（共有 0 条评论）