D5 F

最近见到了好多跟排列有关的状压dp，好像略微会了一点，用 dp[i][s][j]表示第i位状态为s选择j的方案数，然后递推。 

早起大概可以提高人的智商但是会导致人甚至不清，初始化写错了自闭了半个小时

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int n;string s;
int cal(int num){
    int res = 0;
    while(num){
        res+=num%2;
        num>>=1;
    }
    return res;
}
int dp[16][1<<16][16];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>s;s="**"+s;
    for(int i=1;i<=n;i++){
        dp[1][1<<(i-1)][i]=1;
    }
    for(int i=2;i<=n;i++) {
        for (int j=0;j<(1<<n); j++) {
            if(cal(j)!=i)continue;
            for(int k=1;k<=n;k++){
                if(!((1<<k-1)&j))continue;
                for(int l=1;l<=n;l++) {
                    if(!((1<<l-1)&j))continue;
                    if (s[i]=='0') {
                        if(!(l==2*k||k==2*l))
                            dp[i][j][k] += dp[i - 1][j ^ (1 << k - 1)][l];
                    } else {
                        if((l==2*k||k==2*l))
                            dp[i][j][k]+=dp[i-1][j^(1<<k-1)][l];
                    }
                    dp[i][j][k]%=mod;
                }
            }
        }
    }
    ll ans=0;
    for(int k=1;k<=n;k++){
        ans=(ans+dp[n][(1<<n)-1][k])%mod;
    }
    cout<<ans<<endl;
}