ARC 004D - 表現の自由

問題文 : 表現の自由

解法 :

$dp[n][m] :=$ 数$n$ を$m $ 個に分割する方法の総数, としてDPしている. これだけみると状態空間が$nm $ でやばそうだが, 実は1 で分割しない限り$m\leqq32$ くらいで, $n$ としてありえる数も高々$O(\sqrt{n})$ 個なので大丈夫. よってだいたい$O(\sqrt{n})$ 時間でこの問題を解くことが出来る.

コード :

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

#define MOD (1000000007)

using namespace std;

map<pair<int, int>, long long> memo;
map<int, vector<int> > memo2;

long long pow(int n, int m)
{
	long long ret = 1, b = n;
	
	while (m){
		if (m & 1) ret = (ret * b) % MOD;
		b = (b * b) % MOD;
		m >>= 1;
	}
	return (ret);
}

vector<int> divi(int num)
{
	vector<int> ret;
	for (int i = 2; i * i <= num; i++){
		if (num % i == 0){
			ret.push_back(i);
			if (i * i != num) ret.push_back(num / i);
		}
	}
	ret.push_back(num);
	return (ret);
}

int n, m;
long long perm[100001];

long long breakIt(int num, int left)
{
	if (num == 1){
		return ((perm[m] * pow(perm[m - left], MOD - 2) % MOD) * pow(perm[left], MOD - 2) % MOD);
	}
	if (left == 1) return (1);
	
	if (memo.count(make_pair(num, left)) != 0){
		return (memo[make_pair(num, left)]);
	}
	
	long long ret = 0;
	
	vector<int> d;
	if (memo2.count(num) != 0) d = memo2[num];
	else {
		d = divi(num);
		memo2[num] = d;
	}
	
	for (int i = 0; i < d.size(); i++){
		ret = (ret + breakIt(num / d[i], left - 1)) % MOD;
	}
	
	return (memo[make_pair(num, left)] = ret);
}

int main()
{
	scanf("%d %d", &n, &m);
	if (n < 0) n = -n;
	
	perm[0] = 1;
	for (int i = 1; i <= 100000; i++) perm[i] = (i * perm[i - 1]) % MOD;
	
	printf("%lld\n", (breakIt(n, m) * pow(2, m - 1)) % MOD);
	
	return (0);
}