noi.ac #45 计数

$des$

给定 $n$ 的全排列 + 一个值域属于 $[1, n]$ 的元素构成长度为 $n + 1$ 的序列

问长度为 $i$ 的本质不同的子序列的个数

$sol$

小学计数题

记 $p + 1, q - 1$ 的元素相同

从起点到第一个相同元素长度 $p$

从终点到第二个相同元素长度 $q$

对于长度为 $i$ 的本质不同的子序列的个数

可以用全部的答案 - 出现重复的个数

显然全部的答案 $n + 1 \choose i$

对于重复的答案，只存在于重复的元素存在于挑选的元素中的时候

这样的话，挑选的元素只剩下 $i - 1$ 个

枚举在 $[1, p]$ 中挑选 $x$ 个，在 $[q, n + 1]$ 中挑选 $i - 1 - x$ 个统计答案

。。。

这样枚举的就非常zz啊

重复的方案数显然就是 $ q + p \choose i - 1$

时间复杂度 $O(nlogmod)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, Mod = 1e9 + 7;

#define gc getchar()

inline int read() {int x = 0; char c = gc;while(c < '0' || c > '9') c = gc;

while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}

#define LL long long

#define Rep(i, a, b) for(int i = a; i <= b; i ++)

LL fac[N] = {1};

bool vis[N];

LL n, a[N];

LL q, p;

LL Ksm(LL a, LL b) {

	LL ret = 1;

	while(b) {if(b & 1) ret = ret * a % Mod; a = a * a % Mod; b >>= 1;}

	return ret;

}

LL C(LL n_, LL m) {

	if(n_ < m || m == 0) return 0;

	return (fac[n_] * Ksm(((fac[m] * fac[n_ - m]) % Mod), Mod - 2)) % Mod;

}

int main() {

	n = read();

	Rep(i, 1, n + 1) fac[i] = (fac[i - 1] * i) % Mod;

	Rep(i, 1, n + 1) {

	    a[i] = read();

		if(vis[a[i]]) {

			p = n + 1 - i;

			Rep(j, 1, i) if(a[j] == a[i]) {q = j - 1; break;}

			break;

		}

		vis[a[i]] = 1;

	}

	Rep(i, 1, n + 1) {

		LL a = C(n + 1, i), b = C(q + p, i - 1);

		LL Answer;

		if(i == 1) Answer = a - b - 1;

		else Answer = a - b;

		if(Answer < 0) Answer += Mod;

		cout << Answer << "\n";

	}

	return 0;

}

巴特西

noi.ac #45 计数

最新文章

热门文章