Codeforces Round 856 (Div. 2)补题——C、D题

C. 《Scoring Subsequences》（贪心 &思维）

https://codeforces.com/contest/1794/problem/C

题意：
  数组的得分为所有数的乘积除以长度的阶乘，给你一个不下降子序列，问你 $1~i$ 的前缀的子序列的最大得分的最长长度是多少，每个前缀输出一个整数，n <= 2e5。

思路：
  我们可以发现答案一定是单调不递减的，考虑长度不变，向右平移一格，答案一定不会比当前更小，然后我们考虑长度增加1是否会让答案变小。由于我们选取的子序列一定是后缀，所以我们考虑从后面选数然后判断他是否比数组长度大，即乘上的数是否大于1即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N]; 
int n;

void solve(){	
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int k = 1;
	for(int i = 1; i <= n; i++){
		while(k < i && a[i - k] > k) k++;  //贪心地选取后缀 
		printf("%d%c", k, " \n"[i == n]); 
	}
}

int main(){
	int T = 1;
	scanf("%d", &T);
	while(T -- ){
		solve();
	}
	return 0;
}

D.《Counting Factorizations》（dp&组合数）

https://codeforces.com/contest/1794/problem/D

思路：

首先必须要清楚几个点：

• 质数的种类一定要大于等于 $n$。
• 在每一种方案中的底数中，每种质数只能出现一次。
• 在指数中可以出现多次。

状态表示： 令 $f[i][j]$ 表示只考虑前 $i$ 个数，且选出 $j$ 个质数作为底数的集合的方案数。（类似背包问题）

  这里还需要用到含有重复元素的排列数的计算方式。

  一个数组 $a$ 有 $n$ 个数，统计出每种数的出现次数 $cnt_{a_i}$，那么这个数列的排列数为${\Large \frac{n!}{\prod_{1}^{n} cnt_{a_i}} }$

  一共有 $2n$ 个数，所以选 $n$ 个质数作为底数，那么最后剩下的 $n$ 个数就作为指数。指数的贡献为 ${\Large \frac{n!}{\prod_{1}^{n} cnt_{a_i}} }$。

因此：

• 如果一个数不是质数，那么它只能当做指数，它的数量为 $cnt_{a_i}$。
• 否则如果是质数，那么它可以当做底数，此时和它相等的数的其它数都只能当做指数，所以它对应的指数数量为 $cnt_{a_i} - 1$。

由此可以得到转移方程：

• 如果不是质数 $\large f[i][j] = \frac{f[i - 1][j]}{!cnt_{a_i}}$
• 如果是质数 ${\large f[i][j] = \frac{f[i - 1][j - 1]}{!(cnt_{a_i} - 1)} }$

注意：
  由于我们按照公式计算了，所以最终dp的时候需要去重，否则会重复计算。

AC代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 5010, M = 1e6 + 10, MOD = 998244353;
int a[N], cnt[M];
int f[N][N];
bool vis[M];
int primes[M], k;
bool st[M];
int fact[N], inv[N];
int n; 

int qmi(int a, int k){
	int ans = 1;
	while(k){
		if(k & 1) ans = 1LL* ans * a % MOD;
		a = 1LL* a * a % MOD;
		k >>= 1;
	}
	return ans;
}

void get_primes(int n){
	st[1] = true;  //会用到1，所以需要标记一下是非质数 
	for(int i = 2; i <= n; i++){
		if(!st[i]) primes[k++] = i;
		for(int j = 0; primes[j] <= n / i; j++){
			st[primes[j] * i] = true;
			if(i % primes[j] == 0) break;
		}
	}
}

void get_fact(int n){
	fact[0] = inv[0] = 1;
	for(int i = 1; i <= n; i++) {
		fact[i] = 1LL* fact[i - 1] * i % MOD;
		inv[i] = 1LL* inv[i - 1] * qmi(i, MOD - 2) % MOD;
	}
}

void solve(){	
	scanf("%d", &n);
	for(int i = 1; i <= 2 * n; i++){
		scanf("%d", &a[i]);
		cnt[a[i]]++;
	}
	//去重后再dp 
	vector<int> b;
	b.push_back(-1);
	for(int i = 1; i <= 2 * n; i++){
		if(!vis[a[i]]) {
			vis[a[i]] = true;
			b.push_back(a[i]);
		}
	}
	f[0][0] = 1;
	for(int i = 1; i <= b.size(); i++){
		for(int j = 0; j <= i && j <= n; j++){
			//作为指数
			f[i][j] = 1LL* f[i - 1][j] * inv[cnt[b[i]]] % MOD; 
		}
		if(!st[b[i]]){ //如果是质数，那么可以作为底数 
			for(int j = 1; j <= i && j <= n; j++){
				f[i][j] = (f[i][j] + 1LL* f[i - 1][j - 1] * inv[cnt[b[i]] - 1] % MOD) % MOD;	
			}			
		}
	}
	printf("%d\n", 1LL* fact[n] * f[b.size()][n] % MOD);
}

int main(){
	int T = 1;
//	scanf("%d", &T);
	get_primes(M - 1);
	get_fact(N - 1);
	while(T -- ){
		solve();
	}
	return 0;
}