C. Array

题目链接

Codeforces Beta Round #53--C. Array

题解

中档题。题意大概是求出一段长度为n的序列,其中的元素可以是1..n,求出满足非严格单调递增与非严格单调递减的序列数目。
对于每一种可能的元素分配方式,均存在的唯一的非严格单调递增排列方式与非严格单调递减的排列方式,当且仅当序列中所有元素都相同时这两种分配方式才等同。所以求出序列的分配方式再减去n即可。而序列的分配方式等同于球同盒不同,盒子允许为空的情况。
如果有n个相同的球放进m个不同的盒子中,盒子允许为空的组合方式有C(m+n-1,n-1)种。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
const ll INF=1ll<<60;
const ll MOD=1000000007;
long long  fac[MAXN], inv[MAXN], input[MAXN];
inline long long C(long long a, long long b) {
    return fac[a] * inv[b] % MOD * inv[a - b] % MOD;
};
int n;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    inv[0] = inv[1] = fac[0] = 1;
    for (int i = 2; i < MAXN; i++) {
        inv[i] = inv[MOD%i] * (MOD - MOD / i) % MOD;
    }
    for (int i = 1; i < MAXN; i++) {
        fac[i] = fac[i - 1] * i%MOD;
        inv[i] = inv[i - 1] * inv[i] % MOD;
    }
    cin>>n;
    cout<<(2*C(2*n-1,n-1)-n)%MOD<<endl;
}

标签: math, combinatorics

添加新评论