P14990 马赛克

发现不美观的四个点中行相同或列相同的两个点颜色不同，所以修改的时候把一行或一列全部变成一样的最优，这样相当于这一行（列）无法做任何贡献，即把这一行（列）删掉。考虑枚举那些列删掉，然后把他们真的删掉，暴力统计总方案，然后设 \(f_s\) 表示把集合 \(s\) 内的行留下来的不美观度，转移直接 \(\mathcal{O}(n)\) 暴力，总时间复杂度 \(\mathcal{O}(2^{n+m}\times n)\)，理论很玄，实际可过。

代码

/*
Luogu P14990 马赛克
2026-03-02
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
#define ull unsigned long long
const int maxn=20;
int f[(1<<12)+10],n,m,k,a[maxn][maxn],b[maxn][maxn],g[maxn][maxn];
ull w[30010];
ull ksm(ull a,int b){
    ull ans=1;
    while(b){
        if(b&1) ans*=a;a*=a;
        b>>=1;
    }
    return ans;
}
void solve(){
    memset(w,0,sizeof(w));
    read(n,m,k);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(a[i][j]);
    for(int s=0;s<(1<<m);s++){
        int h;
        for(int i=1;i<=n;i++){
            int cnt=0;
            for(int j=1;j<=m;j++){
                if(s&(1<<j-1)) continue;
                b[i][++cnt]=a[i][j];
            }
            h=cnt;
        }
        int zz=0;
        for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){
            int z=0;
            for(int k=1;k<=h;k++) for(int l=k+1;l<=h;l++) if(b[i][k]==b[j][l]&&b[j][k]==b[i][l]&&b[i][k]!=b[i][l]) z++;
            g[i][j]=g[j][i]=z;
            zz+=z;
        }
        f[0]=0;
        for(int i=1;i<(1<<n);i++){
            int w=i&-i,lt=i^w,w_id=__lg(w)+1;
            f[i]=f[lt];
            for(int j=lt;j;j-=(j&-j)) f[i]+=g[w_id][__lg(j&-j)+1];
        }
        for(int i=0;i<(1<<n);i++) w[f[i]]++;
    }
    ull ans=0;
    for(int i=0;i<=30000;i++) ans+=ksm(w[i],k);
    write(ans),write('\n');
}
signed main(){
    int T;read(T);
    while(T--) solve();
    return 0;
}