当前位置：首页 > news >正文

数学公式

news 来源：原创 2024/5/4 16:53:32

1、快速幂

typedef long long LL;
LL deal(LL a, LL b)
{
    LL ans= 1;
    while(b)
    {
        if(b & 1)
            ans *=a; 
        b /= 2;
        a = a*a;
    }
    return ans;
}

2、错排

错排问题就是一种递推式，不过它比较著名且常用，所以要熟记！

方法一：
n各有序的元素应有n！种不同的排列。如若一个排列式的所有的元素都不在原来的位置上，则称这个排列为错排。任给一个n，求出1,2,……,n的错排个数Dn共有多少个。
递归关系式为：D(n)=(n-1)(D(n-1)+D(n-2)) //尽量迭代;
D(1)=0,D(2)=1
可以得到:
错排公式为 f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]
其中,n!=1*2*3*.....*n,
特别地,有0!=0,1!=1.

解释：
n 个不同元素的一个错排可由下述两个步骤完成：
第一步，“错排” 1 号元素（将 1 号元素排在第 2 至第 n 个位置之一），有 n - 1 种方法。
第二步，“错排”其余 n - 1 个元素，按如下顺序进行。视第一步的结果，若1号元素落在第 k 个位置，第二步就先把 k 号元素“错排”好， k 号元素的不同排法将导致两类不同的情况发生：
1、 k 号元素排在第1个位置，留下的 n - 2 个元素在与它们的编号集相等的位置集上“错排”，有 f(n -2) 种方法；
2、 k 号元素不排第 1 个位置，这时可将第 1 个位置“看成”第 k 个位置(也就是说本来准备放到k位置为元素，可以放到1位置中),于是形成（包括 k 号元素在内的） n - 1 个元素的“错排”，有 f(n - 1) 种方法。据加法原理，完成第二步共有 f(n - 2)+f(n - 1) 种方法。
根据乘法原理， n 个不同元素的错排种数
f(n) = (n-1)[f(n-2)+f(n-1)] (n>2) 。

证毕。

3、日期公式

//判日期为星期几 
int weekday(Date a){ 
    int tm = a.month>=3 ? (a.month-2) : (a.month+10); 
    int ty = a.month>=3 ? a.year : (a.year-1); 
    return (ty+ty/4-ty/100+ty/400+(int)(2.6*tm-0.2)+a.day)%7; 
}

闰日：

0-->y sumd= y/4- y/100+ y/400; (注意开始和结尾)

日期英文：

一月January 二月February 三月March 四月April 五月May 六月June七月July 八月August 九月September 十月Octorber 十一月November 十二月December

4、康拓展开

template <typename elemType>
LL kangtuo(elemType c[])
{
    LL sum =0, k;
    for(int i=0; i< len; i++)
    {
        k =0;
        for(int j=i+1; j< len; j++)
            if(c[j] <c[i]) k++;
        sum += k* jc[len-i-1];
    } 
    return sum;
}

5、康拓逆展开

#include <cstdio>
#include <cstring>
typedef long long LL;
LL jc[]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600};
char c[15]= {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l'};
char s[15];
int main()
{
    int t; scanf("%d", &t);
    while(t--){
        memset(s, '\0', sizeof(s));
        strcpy(s, c);
        LL m; scanf("%lld", &m);
        LL temp= m-1;
        for(int i=0; i <12; i++){
            LL id= temp/jc[12-i-1];
            printf("%c", s[id]);
            for(int j=id; j< 12- i; j++)
                s[j]=s[j+1];
            temp -= id*jc[12-i-1];        
        }
        printf("\n");
    }    
    return 0;
}