LGJOI-20230808

AzusidNya の部屋 / 2023-08-08 / 原文

大概是赢了。

A

题意：

给定 \(n\)，\(m\)，将 \(m\) 分解为不超过 \(n\) 个 \(n!\) 的因数的和。

\(n \leq 20\)，\(m \leq n!\)

solution:

考虑如何能做到选最少的数分解 \(m\)。贪心的思路一定是从大到小选取 \(n!\) 的因数。直接枚举 \(n!\) 的因数非常困难，因此考虑优化枚举。

对于 \(n!\) 的一个因数 \(x\) ，一定是由若干个不重复的 \(y(y \le n)\) 相乘而成的。

假设 \(x = \prod^n_{i=1}i^{a_i}\)，它可以分解为一段极长的 \(a_i\) 不为 \(0\) 的后缀与剩余部分相乘。那么先将原数拆解为若干个后缀相加的形式再进行调整。

具体而言，定义数列 \(b_i = \large \frac{n!}{i!}\)，先将 \(m\) 分解为若干个 \(b_i\) 的和，然后如果有重复的 \(b_i\) 则合并即可。

容易证明最多会把 \(m\) 分解为 \(n - 1\) 个数相加。

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
int t, n, m;
int frac[35];
int st[305], top;
signed main(){
	cin >> t;
	frac[0] = 1;
	for(int i = 1; i <= 20; i ++)
		frac[i] = frac[i - 1] * i;
	while(t --){
		cin >> n >> m;
		for(int i = 0; i <= n; i ++)
			while(m >= frac[n] / frac[i])
				st[++ top] = frac[n] / frac[i], m -= frac[n] / frac[i];
		int nw = 2, less = 0, ns = 1, cnt = 1;
		st[++ top] = 998244353;
		while(nw <= top + 1){
			if(st[nw] == st[ns])
				cnt ++, st[nw] = 0;
			else{
				st[ns] *= cnt; 
				less += cnt - 1;
				cnt = 0, ns = nw;
				cnt ++;
			}
			nw ++;
		}
 		cout << top - less - 1 << "\n";
		for(int i = 1; i <= top - 1; i ++)
			if(st[i]) cout << st[i] << " ";
		cout << "\n";
		top = 0; 
	}
	return 0;
}