Codeforces 525E Anya and Cubes 中途相遇法

题目链接：点击打开链接

题意：

给定n个数。k个感叹号，常数S

以下给出这n个数。

目标：

随意给当中一些数变成阶乘。至多变k个。

再随意取一些数，使得这些数和恰好为S

问有多少方法。

思路：

三进制状压。中途查找。

#include <stdio.h>

#include <vector>

#include <algorithm>

#include <iostream>

#include <cmath>

#include <map>

#include <string.h>

#include <string>

template <class T>

inline bool rd(T &ret) {

    char c; int sgn;

    if (c = getchar(), c == EOF) return 0;

    while (c != '-' && (c<'0' || c>'9')) c = getchar();

    sgn = (c == '-') ? -1 : 1;

    ret = (c == '-') ? 0 : (c - '0');

    while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');

    ret *= sgn;

    return 1;

}

template <class T>

inline void pt(T x) {

    if (x <0) {

        putchar('-');

        x = -x;

    }

    if (x>9) pt(x / 10);

    putchar(x % 10 + '0');

}

using namespace std;

typedef long long ll;

const double pi = acos(-1.);

const double e = 2.718281828459;

const ll ma = 1e8;

const int N = 2005;

int n, k;

ll a[30], m;

ll jie[1000], hehe;

ll cal(ll x){

    if (x >= hehe)return -1;

    return jie[x];

}

ll re[30];

map<ll, int>mp[2][30];

ll b[30], d[30], top;

ll y[30], t;

ll san[30];

void work(int x){

    for (int i = 0; i < san[top]; i++)

    {

        int cnt = 0;

        ll sum = 0;

        int tmp = i, id = 0;

        while (tmp){

            if ((tmp % 3) == 1){

                cnt++; sum += d[id];

                if (d[id] < 0){ sum = m + 1; break; }

            }

            else if ((tmp % 3) == 2){

                sum += b[id];

            }

            if (cnt >k || sum > m)break;

            tmp /= 3; id++;

        }

        if (cnt <= k && sum <= m)mp[x][cnt][sum]++;

    }

}

int main(){

    while (cin >> n){

        rd(k); rd(m);

        san[0] = 1; for (int i = 1; i < 30; i++)san[i] = san[i - 1] * 3;

        jie[1] = 1;

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

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

            if (m / jie[i] <= i){

                hehe = i + 1; break;

            }

        }

        for (int i = 0; i < n; i++){

            rd(a[i]);

            re[i] = cal(a[i]);

        }

        for (int i = 0; i < n / 2; i++){ b[i] = a[i]; d[i] = re[i]; }

        top = n / 2;

        work(0);

        for (int i = n / 2; i < n; i++){ b[i - n / 2] = a[i]; d[i - n / 2] = re[i]; }

        top = n - n / 2;

        work(1);

        ll ans = 0;

        for (int i = 0; i <= k; i++)

        for (auto it : mp[0][i])

        for (int j = 0; j + i <= k; j++)

        if (mp[1][j].count(m - it.first))

            ans += (ll)it.second * mp[1][j][m - it.first];

        pt(ans);

    }

    return 0;

}