[ABC025D] 25個の整数 题解

nynkqh_yzp · 2023-04-22 22:59:05 · 题解

这题最多只有 25 个数，所以肯定可以用状压解决，但是状压只能判断之前有没有放数，那么我们就可以从小到大依次放数，就只需要判断有没有连续三个位置都选了的情况。

时间复杂度 O(2^n \times n)。

#include <bits/stdc++.h>
using namespace std;
int f[1<<25],s[26],mo=1000000007,v[26];
void jr(int a,int b){
    if(b%5!=0&&b%5!=4&&((a&(1<<b-1))!=0)^((a&(1<<b+1))!=0))
        return;
    if(b/5!=0&&b/5!=4&&((a&(1<<b-5))!=0)^((a&(1<<b+5))!=0))
        return;
    f[a]=(f[a]+f[a^(1<<b)])%mo;
}
int main(){
    for(int i=0;i<25;i++)
        v[i]=-1;
    for(int i=0;i<25;i++){
        scanf("%d",&s[i]);
        if(s[i]!=0)
            v[s[i]-1]=i;
    }
    f[0]=1;
    for(int i=1;i<(1<<25);i++){
        int an=0,j=i;
        while(j){
            an+=(j&1);
            j=j>>1;
        }
        an--;
        if(v[an]!=-1){
            if((i&(1<<v[an]))!=0)
                jr(i,v[an]);
        }
        else{
            for(int k=0;k<25;k++)
                if((i&(1<<k))!=0&&s[k]==0)
                    jr(i,k);
        }
    }
    printf("%d\n",f[(1<<25)-1]);
    return 0;
}