Submission #19833

#	Time	Username	Problem	Language	Result	Execution time	Memory
19833		javelinsman	악수 (kriii4_D)	C++14	5 / 100	4000 ms	9120 KiB

D

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;

typedef long long ll;

typedef pair<vector<int>,int> state;
map<state,ll> mp;
int n;
const ll MOD = 1e9+7;

ll mm(ll x,ll y){
    x%=MOD;
    if(y==0) return 1;
    if(y==1) return x;
    if(y%2) return mm(x,y-1)*x%MOD;
    ll h = mm(x,y/2);
    return h*h%MOD;
}

ll l_div(ll a,ll b){
    return (a*mm(b,MOD-2))%MOD;
}


ll go(const state& st){
    int trash = st.second;
    const vector<int>& v = st.first;

    if(v.size() == 1) return 0;
    if(mp.count(st)){
        return mp[st];
    }

    int depth = 0;
    for(int x:v){
        depth += x*(x-1)/2;
    }
    depth -= trash;

    int left = n*(n-1)/2 - depth;
    mp[st] = 0;

    for(int i=0;i<v.size();i++){
        for(int j=i+1;j<v.size();j++){
            // combine v[i],v[j]
            vector<int> vv;
            for(int k=0;k<v.size();k++){
                if(k!=i && k!=j) vv.push_back(v[k]);
            }
            vv.push_back(v[i]+v[j]);
            sort(vv.begin(), vv.end());
            state ns = make_pair(vv, trash + v[i]*v[j]-1);

            mp[st] += ((go(ns)+1)%MOD * l_div(v[i]*v[j], left))%MOD;
            mp[st] %= MOD;
        }
    }

    if(trash)
        mp[st] += ((go(make_pair(v, trash-1))+1)%MOD) * l_div(trash, left)%MOD;
    mp[st] %= MOD;

    return mp[st];
}

int main(){
    cin>>n;
    vector<int> v(n,1);
    cout<<go(make_pair(v,0));
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95