题目描述

blablabla

样例

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int N = 13;
unordered_map<int,int> mp,cnt;

int a[N]; int n ;
int fab[N] = {1};
int mem[10010][N];
int dfs(int sum,int pre)
{
    if(sum == (1<<n) - 1) return 1;
    if(mem[sum][pre] >= 0) return mem[sum][pre];
    int res = 0;
    for(int i = 1;i <= n;i ++)
    {
        ll t = a[pre] + a[i];
        if((sum>>(i-1))&1 or t > (ll)2e9 or !mp.count(t) ) continue;
        res += dfs(sum + (1<<(i-1)),i);
    }
    return mem[sum][pre] = res;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(),cout.tie(0);
    for(auto &i : mem) for(auto &j : i) j = -1;
    for(int i = 1;i <= 12;i ++) fab[i] = fab[i-1] * i;

    for(int i = 1;i <= 8e5;i ++) mp[i * i]++;
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i],cnt[a[i]] ++;
    int ans = 0;
    for(int i = 1;i <= n;i++)
    {
        ans += dfs(1<<(i-1),i);
    }

    for(auto &i : cnt) ans /= fab[i.second];
    cout << ans;

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla