fzu2282-Wand 조합 수학 곱셈 역원의 세 가지 구법 오열 공식

순서

Wand
제목의 대략적인 의미는 n조의 대응 관계를 제시하고 이를 흐트러뜨리는 것이다. 마지막에 적어도 k조의 대응 관계가 정확한 흐트러짐을 구하는 방식이다. 사고방식은 k에서 n까지 정확한 대응 관계 개수를 매거하고 조합수 Cn(k)*남은 n-k개의 대응 관계가 완전히 잘못된 배열법이다.

1. 공식을 잘못 배열한다

n개의 번호 요소를 n개의 번호 위치에 두면 원소의 번호와 위치 번호가 모두 대응하지 않는 방법수는 dp[n]로 분명히 dp[1]=0, dp[2]=1을 나타낸다.n개의 원소를 오렬하면

(1) 잘못된 (n-1) 위치에 첫 번째 요소 배치하기

(2) 가설(1)에서 첫 번째 요소를 k위치에 두면 두 가지 상황을 고려한다.

첫 번째 원소를 첫 번째 위치에 두는 것은 첫 번째 원소를 첫 번째 원소와 k번째 원소를 교환하는 것과 같다. n-2개 원소를 잘못 배열하는 방법을 점차적으로 고려하는 것이 dp[n-2]의 방법이다.

첫 번째 원소를 n-2개의 다른 첫 번째 위치를 제외한 잘못된 위치, dp[n-1]가지 방법.

=> dp[n] = (n - 1)(dp[n - 1] + dp[n - 2])

2. 곱셈 역원

확장 유클리드 알고리즘은 x와 y가 방정식을 만족시키는 ax+by = gcd(a, b)

를 구하는 데 사용된다.

inline long long ExGCD(long long A, long long B, long long& x, long long& y){
    if(A == 0 && B == 0) return -1;
    if(B == 0){x = 1, y = 0; return A;}
    long long d = ExGCD(B, A % B, y, x);
    y -= A / B * x;
    return d;
}

제목은 나머지를 줘야 하기 때문에 MOD는 보통 1e9+7 같은 대질수이기 때문에 gcd(a, MOD)==1이면 곱셈 역원을 구할 수 있다

long long ModReverse(long long a, long long f){
    long long x, y, d = ExGCD(a, f, x , y);
    if(d == 1){
        if(x % f <= 0) return x % f + f;
        else return x % f;
    }
    return -1;
}

페르마 소정리 MOD가 소수일 때 a^(MOD-1)==1(mod MOD)이므로 a^(MOD-2)는 a모드 MOD의 의미에서의 곱셈 역원으로 빠른 멱으로 모형을 취하면 된다.

시간 복잡도 O(n)의 추이 [1,n]의 역원표(n유도
가령 앞i-1개수의 곱셈과 역원은 모두 MOD mod i +(MOD div i)* i = MOD = 1 개수의 곱셈과 역원이 MOD mod i +(MOD div i) = > (MOD div i) * i = - - (MOD mod i) (mod MOD) = > (mod MOD MOD) (moD MOD) = > i) = > i = = - (mod MOD) = = > i) (MOD MOD MOD)) = = = = 1 modi - 1) (MOD MOD modi - 1) 보다 작기 때문에 MOi (modi mod modi - 1) 는 modi - 1 modi - 1 모i) 는 모모모i 의 경우 다음과 같은 점차적인 관계를 얻을 수 있다

inv[1] = 1;
for(int i = 2; i <= 10000; i++) inv[i] =  inv[MOD % i] * (MOD - MOD / i) % MOD;

3. 조합수

직접 방정식:
점진식:

3. AC 코드

역원표로 쓴 것으로 시계를 치는 것을 비교적 좋아한다

#include 
#include 

using namespace std;

const long long MOD = 1e9 + 7;

long long dp[10007], inv[10007];

int main()
{
    int T, n, k;
    long long C, ans;

    scanf("%d", &T);
    dp[1] = 0, dp[2] = 1, inv[1] = 1;
    for(int i = 3; i <= 10000; i++) dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD) * (i - 1) % MOD;
    for(int i = 2; i <= 10000; i++) inv[i] =  inv[MOD % i] * (MOD - MOD / i) % MOD;
    for(int cas = 1; cas <= T; cas++){
        scanf("%d%d", &n, &k);
        ans = 1, C = n;
        for(int i = 2; i <= k; i++) C = ((C * (n - i + 1) % MOD) * inv[i]) % MOD;
        for(int i = k; i < n; i++){
            ans = (ans + (C * dp[n - i]) % MOD ) % MOD;
            C = ((C * (n - i) % MOD) * inv[i + 1]) % MOD;
        }
        printf("%I64d
", ans);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

fzu2282-Wand 조합 수학 곱셈 역원의 세 가지 구법 오열 공식

순서

1. 공식을 잘못 배열한다

2. 곱셈 역원

3. 조합수

3. AC 코드

좋은 웹페이지 즐겨찾기