Codeforces 525 E Anya and Cubes途中出会い法

2901 ワード

タイトルリンク:クリックしてリンクを開く
タイトル:
与えられたn個の数、k個の感嘆符、定数S
このn個の数を以下に示す.
ターゲット:
任意にその中のいくつかの数を階乗に変えて、多変k個まで.
更に任意にいくつかの数を取って、これらの数とちょうどSになるようにします
どのくらいの方法があるかを聞く.
考え方:
三進形圧、途中で検索します.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
template 
inline bool rd(T &ret) {
    char c; int sgn;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && (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 
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];
mapmp[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;
}

Androidがダイナミックページを開発する際によく使われるLayoutInflaterのインスタンス化の3つの方法

Pandas Data Frame行または列の削除方法drop関数