【搜索】WAR大佬的SET @upcexam6201

时间限制: 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;

}

巴特西

【搜索】WAR大佬的SET @upcexam6201

最新文章

热门文章