chokudaiさんがtwitterでコメントしてたので適当に実装
追記：逆ポーランド全列挙でゴリ押したほうが早そう
string f(vector<string> v) {
if (1 == v.size()) return v[0];
string ret = "(";
rep(i, v.size())ret += v[i];
ret += ")";
return ret;
}
void solver() {
int n; cin >> n;
vector<int>a(n);
rep(i, n)cin >> a[i];
int d; cin >> d;
vector mp(1 << n, map<frac, string>());
rep(i, n) mp[1 << i][a[i]] = f({ to_string(a[i]) });
rep2(i, 1, 1 << n) {
for (int j = (i - 1)&i; j > 0; j = (j - 1)&i) {
int b0 = i ^ j;
int b1 = j;
for (auto[k0, v0] : mp[b0])for (auto[k1, v1] : mp[b1]) {
{
frac nk = (frac)k0 + k1;
string nv = f({ v0,"+",v1 });
mp[i][nk] = nv;
}
{
frac nk = (frac)k0 - k1;
string nv = f({ v0,"-",v1 });
mp[i][nk] = nv;
}
{
frac nk = (frac)k0 * k1;
string nv = f({ v0,"*",v1 });
mp[i][nk] = nv;
}
if (0 != k1) {
frac nk = (frac)k0 / k1;
string nv = f({ v0,"/",v1 });
mp[i][nk] = nv;
}
}
}
}
if (mp[(1 << n) - 1].count(d)) {
cout << mp[(1 << n) - 1][d] << "=";
calc(mp[(1 << n) - 1][d]).output();
}
}
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
using mint = modint998244353;
const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
string convert(vector<string> s) {
// 逆ポーランド→中置記法
vector<string>st;
set<string>set = { "+", "-", "*", "/" };
rep(i, s.size()) {
if (set.count(s[i])) {
string y = st.back();
st.pop_back();
string x = st.back();
st.pop_back();
st.push_back('(' + x + s[i] + y + ')');
}
else {
st.push_back(s[i]);
}
}
return st.back();
}
bool f(vector<int>a, vector<int>b, vector<int>c, int d) {
int idxa = 0;
int idxc = 0;
vector<mint>num;
vector<string> s;
const vector<char>ch = { '+','-','*','/' };
rep(i, b.size()) {
if (0 == b[i]) {// num
s.push_back(to_string(a[idxa]));
num.push_back(a[idxa]);
idxa++;
}
else {// '+','-','*','/'
s.push_back(string() + ch[c[idxc]]);
mint y = num.back();
num.pop_back();
mint x = num.back();
num.pop_back();
if (0 == c[idxc])num.push_back(x + y);
else if (1 == c[idxc])num.push_back(x - y);
else if (2 == c[idxc])num.push_back(x * y);
else if (3 == c[idxc]) {
if (0 == y.val())return false;
num.push_back(x / y);
}
idxc++;
}
}
if (num.back() == d) {
cout << convert(s) << endl;
return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int>a(n);
rep(i, n)cin >> a[i];
sort(all(a));
int ans; cin >> ans;
vector<vector<int>>vec;// 0数字、1記号
auto dfs = [&](auto self, int n, int c, vector<int>v)->void {
if (0 == n && 0 == c) {
vec.push_back(v);
return;
}
int un = a.size() - n;
int uc = a.size() - 1 - c;
if (un + 1 > uc && n) {
v.push_back(0);
self(self, n - 1, c, v);
v.pop_back();
}
if (un > uc + 1 && c) {
v.push_back(1);
self(self, n, c - 1, v);
v.pop_back();
}
};
dfs(dfs, a.size(), a.size() - 1, {});
vector<vector<int>>vc;
int bit = 1 << (2 * n - 2);
rep(i, bit) {
int ci = i;
vector<int>tmp;
rep(j, n - 1) {
tmp.push_back(ci % 4);
ci /= 4;
}
vc.push_back(tmp);
}
//cout << vec.size() << endl;
//cout << vc.size() << endl;
do {
rep(i, vec.size()) rep(j, vc.size()) {
auto res = f(a, vec[i], vc[j], ans);
if (res) return 0;
}
} while (next_permutation(a.begin(), a.end()));
return 0;
}マルチテストケース
11 4 2 5 5 9 13 4 4 8 8 9 23 4 3 5 8 9 24 4 1 3 5 7 19 6 1 2 2 6 7 9 16 6 1 2 3 3 3 9 13 6 1 4 5 6 6 6 9 4 1 5 6 7 13 5 1 2 3 6 6 24 4 2 3 4 4 19 5 2 4 7 9 9 14
