제출 #1286675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286675		papaulo	순열 (APIO22_perm)	C++20	0 / 100	1098 ms	56840 KiB

perm

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

using ll = long long;

#define MAXV (1<<17)
vector<int> primos;
vector<int> dp[MAXV];
map<ll, vector<int>> pans;
int initted=0;

int count_increasing_b(const vector<int>& v) {
  vector<int> dp(v.size() + 1, 0);
  dp[0] = 1;
  for (int x : v)
  {
  	for (int i = 0; i <= x; i++)
  	{
  		dp[x+1] += dp[i];
  	}
  }
  int result = 0;
  for (int i = 0; i <= (int)v.size(); i++){
  	result += dp[i];
  }
  return result;
}

int isdiv(ll v) {
    for(auto i : primos) {
        while(v%i==0) v/=i;
    }
    return v==1;
}

vector<int> add(vector<int> a, vector<int> b) {
	vector<int> ans;
	for(auto v : a) ans.push_back(v+(int)b.size());
	for(auto v : b) ans.push_back(v);
	return ans;
}

vector<int> multiply(vector<int> a, vector<int> b) {
	vector<int> ans;
	for(auto v : a) ans.push_back(v);
	for(auto v : b) ans.push_back(v+(int)a.size());
	return ans;
}

vector<int> getdp(ll v) {
	ll ov=v;
	if(pans.find(v)!=pans.end()) return pans[v];
    vector<int> ans(100);
	ll diff=0;
    while((int)ans.size()>90) {
        while(!isdiv(v)) {
            --v;
            ++diff;
        }
        ans=vector<int>();
        ll prod=1;
		ll val=v;
        for(auto i : primos) {
            while(val%i==0) {
                val/=i;
                prod*=i;
                if(prod>=MAXV) {
                    prod/=i;
                    ans=multiply(ans, dp[prod]);
                    prod=i;
                }
            }
        }
        ans=multiply(ans, dp[prod]);
		ans=add(ans, dp[diff+1]);
		++diff;
		--v;
		//cout << v << " " << diff << " " << ans.size() << endl;
    }
	pans[ov]=ans;
    return ans;
}

int primo(int v) {
    for(int i=2;i*i<=v;i++) if(v%i==0) return 0;
    return 1;
}

void init() {
	if(initted) return;
	initted=1;
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
	for(int i=0;i<MAXV;i++) dp[i]=vector<int>(100);
    for(int n=0;n<=10;n++) {
        vector<int> vec;
        for(int i=0;i<n;i++) vec.push_back(i);
        do {
            int ct=count_increasing_b(vec);
            if(ct>MAXV) continue;
            if(n<(int)dp[ct].size()) dp[ct]=vec;
        } while(next_permutation(vec.begin(), vec.end()));
    }
    auto start=chrono::high_resolution_clock::now();
    for(int k=0;k<5;k++) {
        for(int i=2;i<MAXV;i++) {
            int l=min(i, 1024);
            for(int j=1;j<l;j++) {
                if((int)dp[j].size()+(int)dp[i-j+1].size()<(int)dp[i].size()) dp[i]=add(dp[j], dp[i-j+1]);
            }
        }
        for(int i=2;i<MAXV;i++) {
            for(int j=2, k=2*i;j<=i&&k<MAXV;j++,k+=i) {
                if((int)dp[i].size()+(int)dp[j].size()<(int)dp[k].size()) dp[k]=multiply(dp[i], dp[j]);
            }
        }
    }
    for(int i=2;i<MAXV;i++) {
        if(primo(i)) primos.push_back(i);
    }
}

vector<int> construct_permutation(long long k) {
	init();
	return getdp(k);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 90