atcoder D - 11（组合数学）

题目链接：http://arc077.contest.atcoder.jp/tasks/arc077_b

题解：有n+1个数只有一个数字是有重复出现的，要求一共有多少不同的组合显然和这两个数的位置有关系，具体看一下代码就能理解了

就是组合数学看一下代码就好理解了，这题比较简单不多加解释。

#include <iostream>

#include <cstring>

#include <cmath>

#include <cstdio>

#define mod 1000000007

using namespace std;

const int M = 1e5 + 10;

typedef long long ll;

int a[M];

bool vis[M];

ll up[M] , down[M] , up2[M] , down2[M];

ll inv(ll a) {

    return a == 1 ? 1 : (ll)(mod - mod / a) * inv(mod % a) % mod;

}

int main() {

    int n;

    scanf("%d" , &n);

    for(int i = 1 ; i <= n + 1 ; i++) scanf("%d" , &a[i]);

    memset(vis , 0 , sizeof(vis));

    int pos1 = 0 , pos2 = 0 , gg;

    for(int i = 1 ; i <= n + 1 ; i++) {

        if(!vis[a[i]]) {

            vis[a[i]] = true;

            continue;

        }

        else {

            pos2 = i;

            gg = a[i];

            break;

        }

    }

    for(int i = 1 ; i <= n + 1 ; i++) {

        if(a[i] == gg) {

            pos1 = i;

            break;

        }

    }

    int num = n - pos2 + 1;

    int num2 = pos1 - 1;

    num += num2;

    up[0] = 1 , down[0] = 1 , up2[0] = 1 , down2[0] = 1;

    n++;

    for(int i = 1 ; i <= n / 2 ; i++) up[i] = up[i - 1] * (n - i + 1) % mod , down[i] = down[i - 1] * i % mod;

    for(int i = n / 2 + 1 ; i <= n ; i++) up[i] = up[n - i] , down[i] = down[n - i];

    for(int i = 1 ; i <= num / 2 ; i++) up2[i] = up2[i - 1] * (num - i + 1) % mod , down2[i] = down2[i - 1] * i % mod;

    for(int i = num / 2 + 1 ; i <= num ; i++) up2[i] = up2[num - i] , down2[i] = down2[num - i];

    for(int i = 1 ; i <= n ; i++) {

        ll sum = 0;

        if(i == 1) {

            printf("%lld\n" , (ll)(n - 1));

        }

        else {

            sum += up[i] * inv(down[i]) % mod;

            if(num >= i - 1 && num > 0) sum -= up2[i - 1] * inv(down2[i - 1]) % mod;

            printf("%lld\n" , (sum + mod) % mod);

        }

    }

    return 0;

}

巴特西

atcoder D - 11（组合数学）

最新文章

热门文章