Non saprei che tag mettere ma oggi ho trovato due pezzi di codici davvero strani, fanno esattamente la stessa cosa solo che uno nella complessità ha un fattore N aggiuntivo.
(constraints: N <= 21)
Codice con complessità O(N^2*2^N):
for(int i = 0;i<n;i++){
for(int j=0; j < (1<<n);j++)if(__builtin_popcount(j)==i+1){
//ciclo da 0 a N qua
}
}
Codice con complessità O(N*2^N):
for(int j=0; j < (1<<n);j++){
int i = __builtin_popcount(j)-1;
//ciclo da 0 a N qua
}
L’unica differenza tra i due codici mi sembra essere che nel primo la funzione __builtin_popcount venga chiamata molte più volte, mentre il ciclo all’interno (che ho omesso) viene eseguito esattamente lo stesso numero di volte con gli stessi valori. Tuttavia il primo codice risulta leggermente più veloce. C’è probabilmente qualcosa che mi sto perdendo ma non riesco proprio a capire cosa.
Per chi fosse interessato questo è il problema, mentre questo è il codice completo:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
using ll = long long;
constexpr ll mod = 1000000007;
void solve();
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
// cin>>t;
rep(i,t){
solve();
}
}
void solve(){
int n;
cin>>n;
vector<vector<int>> matr(n,vector<int>(n));
rep(i,n)rep(j,n)cin>>matr[i][j];
vector<ll> dp(1<<n);
dp[0]=1;
rep(i,n){
rep(j,(1<<n))if(__builtin_popcount(j)==i+1){
rep(z,n)if((j & (1<<z)) && matr[i][z]){
dp[j]=(dp[j] + dp[j ^ (1<<z)])%mod;
}
}
}
cout<<dp[(1<<n)-1]<<'\n';
}