【搜索】WAR大佬的SET @upcexam6201

时间:2020-12-27 16:18:17

时间限制: 1 Sec 内存限制: 128 MB

题目描述

WAR大佬认为一个包含重复元素的集合认为是优美的,当且仅当集合中的元素的和等于他们的积。

求包含n个元素的优美的集合的个数。

WAR大佬当然会啊,他只是想考考你。

输入

一个正整数n(2<=n<=1000)

输出

一个数ans表示集合的个数

样例输入

5

样例输出

3

提示

1+1+1+2+5=1*1*1*2*5

1+1+1+3+3=1*1*1*3*3

1+1+2+2+2=1*1*2*2*2

dfs,注意题目说了必须要有重复元素

剪枝条件是后面每位都用当前数且exmul*幂大于exsum+和时

#define FILE() freopen("../../in.txt","r",stdin)
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
const int maxn = 1005; ll fstpow(ll a,ll n) {
ll res = 1;
while(n) {
if(n&1)res*=a;
a*=a;
n>>=1;
}
return res;
} ll dfs(ll _digit,ll _num,ll _exmul,ll _exsum) {
_exmul*=_num;
_exsum+=_num;
if(_digit==1) {
if(_exmul==_exsum)return 1;
else return 0;
}
ll ans = 0;
for(ll i=_num;; i++) {
if(_exmul*fstpow(i,_digit-1)>_exsum+i*(_digit-1))break;
if(_digit==2&&_num==1)break;
ans+=dfs(_digit-1,i,_exmul,_exsum);
}
return ans;
} int main() {
// FILE();
// freopen("../../out.txt","w",stdout);
ll n;
scanf("%lld",&n);
if(n==2||n==3)printf("0\n");
else {
ll ans = 0;
ll digit = min(n,32ll);
ans=dfs(digit,1,1,n-digit);
printf("%lld\n",ans);
}
return 0;
}