【51nod】1251 Fox序列的数量

题解

容斥题

我们枚举出现次数最多的数出现了K次

然后我们需要计算的序列是所有数字出现个数都不超过K - 1次

我们枚举不合法的数字的数目j，说明这个排列里除了我们固定出现K次的数至少有j个数是不合法的，先让这j个数每个数出现k次，然后再随意排列

j最大是N / K

那么复杂度就是调和级数了

代码

#include <bits/stdc++.h>

//#define ivorysi

#define enter putchar('\n')

#define space putchar(' ')

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define eps 1e-8

#define mo 974711

#define pii pair<int,int>

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 1000000007;

const int MAXN = 200000;

int fac[MAXN + 5],inv[MAXN + 5],invfac[MAXN + 5],N,M,ans;

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

int C(int n,int m) {

    if(n < m) return 0;

    return mul(mul(fac[n],invfac[m]),invfac[n - m]);

}

void Init() {

    fac[0] = 1;

    for(int i = 1 ; i <= MAXN ; ++i) fac[i] = mul(fac[i - 1],i);

    inv[0] = 1;inv[1] = 1;

    for(int i = 2 ; i <= MAXN ; ++i) inv[i] = mul(inv[MOD % i],MOD - (MOD / i));

    invfac[0] = 1;

    for(int i = 1 ; i <= MAXN ; ++i) invfac[i] = mul(invfac[i - 1],inv[i]);

}

void Solve() {

    read(N);read(M);

    if(M == 1) {out(1);enter;return;}

    ans = 0;

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

	ans = inc(ans,mul(M,C(N + M - i - 2,M - 2)));

	for(int j = 1 ; j <= min(N / i,M) ; ++j) {

	    int s = mul(mul(M,C(N + M - i * j - i - 2,M - 2)),C(M - 1,j));

	    if(j & 1) ans = inc(ans,MOD - s);

	    else ans = inc(ans,s);

	}

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Init();

    int T;

    read(T);

    while(T--) {

	Solve();

    }

    return 0;

}

今天状态实在不好><刷的题太少……会的还不能一次A，看到代码量过大的题就给扔了

尽快调整过来吧

NOI前立最后一个flag是单纯形……再学我觉得也学不会啥了……

不要沉湎于无意义的想念了……

巴特西

【51nod】1251 Fox序列的数量

题解

代码

最新文章

热门文章