yukicoder : No.473 和と積の和

なんか似たようなのSRMで見たことある。
http://yukicoder.me/problems/no/473

問題

N要素からなる正整数の多重集合Sを考える。
S中の2要素a,b∈Sを選び、(a+b+ab)で置き換えもとのa,bを削除する、という処理を要素が１つになるまで繰り返す。
最終的に正整数Xが残せるようなSは何通りか。

解法

要素の選び順は実は関係なく、最初のSによって最後に残る要素は確定する。
Sの各要素をs[0]...s[N-1]とすると、最終的に残る要素はである。

よって、この問題は(X+1)をN個の2以上の約数の積に置き換える問題をみなすことができる。
(X+1)の約数をD[0..d]とする。
以下の状態を考え、f(N,0,1)を答えればよい。
f(n, x, p) := (D[0]+1)...(D[x]+1)のうち重複を許して(N-n)個選びその積がpであるとき、残りのn個を選んで積が(X+1)になる選び方

高度合成数を考えるとdは1000以上となる。
f(n,x,p)を愚直に埋めようとするとO(N*d^2)かかりTLEかつMLEするので、その後(X+1)を超えるのが確定的な場合は枝狩りするなどしよう。

ll N,X;
vector<ll> V;
map<int,int> R;

map<int,int> memo[101][1500];
ll P[1500][105];


ll dfs(int left,int id,ll v) {
	if(left==0) return v==X;
	if(memo[left][id].count(v)) return memo[left][id][v];
	if(v*P[id][left]>X) return 0;
	ll ret=0;
	
	int x;
	for(x=id;x<V.size();x++) if(v*V[x]<=X && R.count(v*V[x])) ret += dfs(left-1,x,v*V[x]);
	
	return memo[left][id][v]=ret;
	
}

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	X++;
	V=enumdiv(X);
	FOR(i,V.size()) {
		R[V[i]]=i;
		P[i][0]=1;
		FOR(x,100) P[i][x+1]=min(P[i][x]*V[i],1LL<<30);
	}
	
	
	cout<<dfs(N,1,1)<<endl;
	
	
}

まとめ

TLE/MLE対応に少し手間取った。