수론 소지식(오열, 스탈린)

스탈린 수: 위키백과 스틸링 수 참고
첫 번째 유형의 Stirling 수는 양과 음이 있고 절대 값은 n개의 원소의 항목을 k개의 고리로 나누어 배열하는 방법 수이다.
주어진 s(n,0)= 0, s(1,1)= 1, 귀속 관계 S(n,k)=S(n−1,k−1)+(n-1)S(n−1,k)
두 번째 유형 Stirling 수는 n개 요소의 집합이 k개의 등가류를 정의하는 방법의 수입니다.
주어진 S(n, n)=S(n, 1)= 1, 귀속 관계 S(n, k)=S(n−1, k−1)+kS(n−1, k)
첫 번째 유형 스틸링 수의 샘플:hdu3625
공식적인 유도 프로세스:
n개수는 0조로 나뉘어 0에서 배열되고, 한 수는 한 조로 나뉘어 배열된다.
n개수는 k조로 나뉜다. (새로운 수는 자기 조의 나머지 n-1개수는 k-1조로 나뉜다) 와 (n-1개는 k조로 나뉜다. n-1의 삽입 방식이 있다)
코드:

#include <iostream>
#include <stdio.h>
using namespace std;
long long num[22][22];
long long  fun(int n)// 
{
	long long ss=1;
	while(n>0) {ss*=n;n--;}
	return ss;
}
int  main()
{
	int t,i,j;
	cin>>t;
	memset(num,0,sizeof(num));//stirling 
	num[1][1]=1;
	for (i=2;i<21;i++)
	{
		for (j=1;j<=i;j++)
		{
			num[i][j]=num[i-1][j-1]+(i-1)*num[i-1][j];
		}
	}
	while (t--)
	{
		int n,k;
		cin>>n>>k;
		long long rr=0;
		for (i=1;i<=k;i++)
		{
			rr+=num[n][i]-num[n-1][i-1];// 1 
		}
		double re=(double)rr/fun(n);
		printf("%.4lf
",re);
	}
	return 0;
}

스탈린 공식:
n의 곱하기 근사값을 구하려면:
n!=sqrt(2*PI*n)*(PI/e)^n;
비트: len=(int)ceil((N*log(N)-N+log(2*N*PI)/2)/log(10);/////ceil 상계, 즉 어떤 값보다 작지 않은 최소 정수 구하기
잘못된 배열 공식:
n 각 질서정연한 원소는 n이 있어야 한다!종별 배열.만약 하나의 배열식의 모든 원소가 원래의 위치에 없다면 이 배열을 잘못된 배열이라고 부른다.n을 주든지 하나, 둘을 구하든지, n의 잘못된 배열 개수 dn은 모두 몇 개입니까?
귀속 관계식: d(n)= (n-1) (d(n-1) + d(n-2)
d(1)=0,d(2)=1
획득:
잘못된 공식은 dn=n!(1-1/2!+1/3!-.....+(-1)n/n!)그중, n!=1*2*3*.....*n, 특별히, 0이 있다!=0,1!=일.
피보나치 수열의 근사치:
Fn=(1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n](n=1,2,3.....)
양쪽을 동시에 맞출 수 있음:log10(Fn)=-0.5*log10(5.0)+((double)n)n)n*log(f)/log(10.0)+log10(1-(1-≠5)/(1+≠5))^n)
그중 f=(sqrt(5.0)+1.0)/2.0;log10(1-(1-≠5)/(1+≠5))^n)이 0에 가까워지기 때문에log10(Fn)=-0.5*log10(5.0)+((double)n)n)n)n*log(f)/log(10.0);
샘플: hdu1568 코드:

#include<iostream>
#include<cmath>
#include<cstdio> 
using namespace std;
const double f = (sqrt(5.0)+1.0)/2;
int main()
{
    int n,i;
    double bit;
    int fac[21] = { 0 , 1 };
    for(i = 2; i < 21; i++) 
        fac[i] = fac[i-1] + fac [i-2];
    while(cin >> n)
    {
        if(n <= 20) {
            cout << fac[n] << endl;
            continue;
        }
        else{
            bit = -0.5*log(5.0)/log(10.0)+((double)n)*log(f)/log(10.0);
            bit = bit - floor(bit); 
            bit = pow(10.0,bit); 
            while(bit < 1000) 
                bit = 10.0 * bit; 
            cout << (int)bit << endl;    
        }
    }
    return 0;
}