Submission #41881127

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}

const int N = 18;
bool solved[N][1<<18][N]; // mint = 0并不表示没计算过
mint ans[N][1<<18][N];

char s[N][N+1];

int m;

mint f(int r,int mask,int c){
  if(mask == 0) return 1; // 所有列都删除了
  if(r == -1) return 1; // 所有行都删除了
  assert(r>=0);
  assert(mask < (1<<m));
  assert(c >= 0);
  mint &res = ans[r][mask][c];
  if(solved[r][mask][c]) return res;
  if(!(mask & (1<<c))) { // 这列已经删掉
    if(c) return res = f(r,mask,c-1);
    else  return res = f(r-1,mask,m-1);
  }
  solved[r][mask][c] = true;
  int r1 = 0; // 同 row 1
  int rq = 0; // 同 row question
  int c1 = 0; // 同 col 1
  int cq = 0; // 同 col question
  rep(j,0,c) { // 左侧点统计时注意已经删除的列 看作是1
    r1 += s[r][j] == '1' or !(mask & (1<<j));
    rq += s[r][j] == '?' and (mask & (1<<j));
  }
  rep(i,0,r) {
    c1 += s[i][c] == '1';
    cq += s[i][c] == '?';
  }
  auto rmNothing=[&]()->mint{ return c?f(r,mask       ,c-1):f(r-1,mask       ,m-1); };
  auto rmCol    =[&]()->mint{ return c?f(r,mask-(1<<c),c-1):f(r-1,mask-(1<<c),m-1); };
  auto rmRowCol =[&]()->mint{ return f(r-1,mask-(1<<c),m-1);};
  auto rmRow    =[&]()->mint{ return f(r-1,mask,m-1); };

  auto fill0=[&](){ res += rmNothing(); }; // 填0
  auto fill1=[&](){ // 填1
    // 行列至少一个满
    if(r1 == c and c1 == r) { // 行列已经全满
     res += rmRowCol();
    }else if(r1 == c) { // 行已经满,列任意
      res += rmRow();
    }else if(c1 == r) { // 列已经满,行任意
      res += rmCol();
    }else if(r1+rq != c and c1+cq == r) { // 行不能满，列可以满
      res += rmCol();
    }else if(r1+rq == c and c1+cq != r) { // 行可以满, 列不能满
      res += rmRow();
    }else if(r1+rq == c and c1+cq == r) { // 都可以满, 但都没满, 容斥
      res += rmRow() + rmCol() - rmRowCol();
    }else{ // 都不能满
      // 失败
    }
  };

  if(s[r][c] == '0'){ // 忽略行列选择
    fill0();
  }else if(s[r][c] == '1'){
    fill1();
  }else{ // == '?'
    fill0();
    fill1();
  }
  return res;
}


int main(){
  int n=read();
  m=read();
  rep(i,0,n) scanf("%s",s[i]);
  printf("%d\n",f(n-1,(1<<m)-1,m-1).val());
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:8:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    8 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:83:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   83 |   rep(i,0,n) scanf("%s",s[i]);
      |              ~~~~~^~~~~~~~~~~

Judge Result