首页 > 其他 > 详细

The Preliminary Contest for ICPC Asia Shanghai 2019

时间:2019-09-16 00:36:43      阅读:205      评论:0      收藏:0      [点我收藏+]

D. Counting Sequences I

暴力搜索。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

map<vector<short>, short> m;
vector<short> vec;

void calc(int num1) {
    vector<short> tmp;
    if(num1)
        tmp.push_back(num1);
    int n = vec.size();
    int cur = 1;
    for(int i = 1; i < n; ++i) {
        if(vec[i] != vec[i - 1]) {
            tmp.push_back(cur);
            cur = 1;
        } else
            ++cur;
    }
    tmp.push_back(cur);
    sort(tmp.begin(), tmp.end());
    m[tmp]++;
}

void dfs(int last, int cur, ll pro, int sum) {
    for(int i = last; i <= 3000; ++i) {
        int tcur = cur + 1;
        ll tpro = pro * i;
        int tsum = sum + i;
        if(tpro - tsum + tcur > 3000)
            break;

        vec.push_back(i);
        calc(tpro - tsum);
        if(tpro * i - (tsum + i) + (tcur + 1) <= 3000)
            dfs(i, tcur, tpro, tsum);
        vec.pop_back();
    }
}

ll qpow(ll x, int n) {
    ll res = 1;
    while(n) {
        if(n & 1)
            res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return res;
}

int ans[3005], prod[3005], invprod[3005];

void Init() {
    dfs(2, 0, 1, 0);
    prod[0] = 1;
    for(int i = 1; i <= 3000; ++i) {
        prod[i] = 1ll * prod[i - 1] * i % MOD;
        invprod[i] = qpow(prod[i], MOD - 2);
    }
    for(auto mi : m) {
        ll sum = 1;
        int len = 0;
        for(auto vi : mi.first) {
            len += vi;
            sum = (sum * invprod[vi]) % MOD;
        }
        sum = (sum * prod[len]) % MOD;
        sum = (sum * mi.second) % MOD;
        ans[len] = (sum + ans[len]) % MOD;
    }
    ans[0] = ans[1] = 0;
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    Init();
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
}

The Preliminary Contest for ICPC Asia Shanghai 2019

原文:https://www.cnblogs.com/Inko/p/11525037.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!