【Henu ACM Round#18 E】Anya and Cubes

在这里输入题意

【题解】

每个数字有3种选择。
1.选中它。
2.选中它且加阶乘符号
3.不选中它(即计算和的时候不考虑它)

如果我们直接暴力写的话复杂度是\(3^{25}\)

寻求优化。

我们可以用Meet-in-the-middle这个方法。

先求出1..n/2这些数字的组合方式。

用map<ll,ll> dic[25]来存它们的和。

dic[i][j]表示前n/2个数字中选了i个【2】状态的数字,和为j的方案数。

则我们再穷举n/2+1..n这些数字的选择情况。

得到了和sum以及【2】状态的数字个数cnt之后。

答案累加\(∑_0^{k-cnt}dic[i][m-sum]\)

这样复杂度就是\(O(3^{12})\)级别的了。

完全可以接受了

(n=1的时候,n/2等于0,如果你的dfs里面写的条件是now==n/2,应该把它改为now>=n/2,如果不这么改的话,dic[0][0]=1这个会漏掉,

然后右半边就可能会漏解了)

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e6;

const int M = 25;

const int MM = 200e4;

int n,k,a[M+10],bo[M+10],tt;

ll pre[M+10],m,ans;

vector<ll>b[M+1];

int get_num(int cnt,ll x){

    int l = 0,r = b[cnt].size()-1,temp1=-1,temp2=-1;

    while (l <= r){

        int mid = (l+r)>>1;

        if (x<=b[cnt][mid]){

            temp1 = mid;

            r = mid-1;

        }else l = mid+1;

    }

    l = 0,r = b[cnt].size()-1;

    while (l <= r){

        int mid = (l+r)>>1;

        if (x>=b[cnt][mid]){

            temp2 = mid;

            l = mid+1;

        }else r = mid-1;

    }

    if (temp1==-1 || temp2 ==-1 ||  b[cnt][temp1]!=x) return 0;

    else return temp2-temp1+1;

}

void dfs(int now,int ope){

    int st,en;

        if (ope==1)

            st = 1,en = n/2;

        else

            st = n/2+1,en = n;

    if (now>=en+1){

        ll sum = 0;

        int cnt = 0;

        for (int i = st;i <= en;i++){

            if (bo[i]==0) continue;

            if (bo[i]==2){

                if (a[i]>=19) return;

                sum+=pre[a[i]];

                cnt++;

            }else sum+=a[i];

        }

        if (sum > m) return;

        if (ope==1){

            b[cnt].push_back(sum);

        }else{

            for (int i = 0;i <= k-cnt;i++) {

                ans+=get_num(i,m-sum);

            }

        }

        return;

    }

    bo[now] = 0;

    dfs(now+1,ope);

    bo[now] = 1;

    dfs(now+1,ope);

    bo[now] = 2;

    dfs(now+1,ope);

}

int main()

{

    #ifdef LOCAL_DEFINE

        freopen("rush_in.txt","r",stdin);

    #endif

   ios::sync_with_stdio(0),cin.tie(0);

    pre[0] = 1;

    for (int i = 1; ;i++){

        pre[i] = pre[i-1]*i;

        if (pre[i]>1e16+10) break;

    }

    cin >> n >> k >> m;

    for (int i = 1;i <= n;i++) cin >> a[i];

    dfs(1,1);

    for (int i = 0;i <= k;i++) sort(b[i].begin(),b[i].end());

    dfs(n/2+1,2);

    cout<<ans<<endl;

    return 0;

}

巴特西

【Henu ACM Round#18 E】Anya and Cubes

最新文章

热门文章