紫书习题 10-25 UVa 1575 (有重复元素的全排列+暴搜）

我一开始以为有什么很牛逼的方法来做，然后一直没有思路

后来看了https://blog.csdn.net/zju2016/article/details/78562932的博客

竟然是暴搜？？？？？？？？？？？/

好我服了

大致思路：素数的范围在100以内

因为要求尽量小，所以素数取得要尽量小

在100内的素数有20多个，这20多个配合上幂

是可以凑到2的63次方那么大的

那么我们枚举素数，得出的组合个数再与题目给的比较

然后这里有个贪心，因为要尽量小，所以素数小的要取多一些

大的取小一些，所以素数幂应该随着素数增大越来越小

然后有个比较难理解的是给一个数字怎么算组合个数

假设p = a1^k1 * a2^k2 ……ak ^ kr

其实就是算有重复元素的全排列

可以理解为有k1个a， k2个b， k3个c ……

然后求全排列

那么我们设一共有n个元素，即k1 + k2 ……kr = n

那么假设最终答案为x

那么x * k1! * k2! ……kr! = n!

也就是说如果不看重复，总的排列数为n的阶乘

那么如果看重复就是x种，而每一种里面每一块

重复的元素都可以做一个小的全排列。

例如k1个a，就有k1 !个方案

根据乘法原理，x * k1! * k2!……kr! 所得出的也是不看重复下全排列的个数

所以移项可以得x = n! /( k1 ! * k2!……kr!)

讲这个干嘛呢？

主要是为了解释加入了新元素组合总数会有什么变化

设在原来的基础上新加入了k个相同的元素

那么新的方案x1 = （n+k）! /( k1 ! * k2!……kr! * k!)

那么我们用x1/x，可以算出

x1 / x = (n+k)! / (n!*k!)

看到(n+k)! / (n!*k!)你想到了什么？？？？？

非常巧的是，这就是c(n+k, k)

所以我们可以预处理组合数。

#include<cstdio>

#include<cstring>

#include<vector>

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

using namespace std;

typedef unsigned long long ull;

const int MAXN = 112;

ull c[MAXN][MAXN], n;

bool is_prime[MAXN];

vector<int> prime;

void init()

{

	memset(is_prime, true, sizeof(is_prime)); //线性筛法

	is_prime[0] = is_prime[1] = false;

	REP(i, 2, MAXN)

	{

		if(is_prime[i]) prime.push_back(i);

		REP(j, 0, prime.size())

		{

			if(i * prime[j] >= MAXN) break;

			is_prime[i * prime[j]] = false;

			if(i % prime[j] == 0) break;

		}

	}

	REP(i, 0, MAXN) //推组合数

	{

		c[i][0] = c[i][i] = 1;

		REP(j, 1, i) c[i][j] = c[i-1][j-1] + c[i-1][j];

	}

}

void dfs(ull k, ull& ans, ull now, int ind, int pre, int up) //pre就是幂的总数，ind是当前应该从哪个素数开始用

{                                                            //up是为了保证小的素数取得多，这样更优

	if(k > ans || ind > prime.size() || now > n) return; //超级无敌剪枝

	if(now == n) { ans = k; return; }

	ull t = 1;

	REP(i, 1, up + 1) //枚举当前这个素数的幂

	{

		t *= prime[ind];

		if(k > ans / t) return; //这么写防止溢出

		dfs(k * t, ans, now * c[pre+i][i], ind + 1, pre + i, i); //注意这里now的更新，解析中推过了

	}

}

int main()

{

	init();

	while(~scanf("%llu", &n))

	{

		if(n == 1) { puts("1 2"); continue; } //我觉得2不能分解成素数乘积，组合的个数应该是0

		ull ans = 1ULL << 63;                //但是题目样例是这么给的，那么就特判吧。

		dfs(1, ans, 1, 0, 0, 63);

		printf("%llu %llu\n", n, ans);

	}

	return 0;

}

巴特西

紫书习题 10-25 UVa 1575 (有重复元素的全排列+暴搜）

最新文章

热门文章

巴特西

紫书 习题 10-25 UVa 1575 (有重复元素的全排列+暴搜）

最新文章

热门文章

紫书习题 10-25 UVa 1575 (有重复元素的全排列+暴搜）