PG BATTLE 2022 解答例一覧

AtCoder社による解答はC++のものとなります。

JavaおよびPythonによる解答例はPG BATTLE運営が用意したものとなりますので、ご了承ください。

C++

#include <iostream>
using namespace std;

int main(void)
{
  string s;
  cin >> s;
  cout << "81" << s.substr(1) << endl;
  return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String S = sc.next();
        System.out.println("8190" + S.substring(3));
    }
} 

Python

S = input()
print(f'8190{S[3:]}')

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    
    int N;
    cin>>N;
    
    vector<int> a(N+1);
    vector<char> op(N);
    
    for(int i=0;i<N+1;i++){
        cin>>a[i];
        if(i!=N)cin>>op[i];
    }
    
    int sum = -1;
    
    while(a.size()>0){
        int t = a.back();
        a.pop_back();
        while(true){
            if(a.size()==0)break;
            if(op.back()=='+'){
                op.pop_back();
                t += a.back();
                a.pop_back();
            }
            else{
                op.pop_back();
                break;
            }
        }
        if(sum==-1)sum = t;
        else if(sum!=t){
            cout<<"No"<<endl;
            return 0;
        }
    }
    
    cout<<"Yes"<<endl;
    
    return 0;
} 

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int sum = -1;
        int tmp = sc.nextInt();
        for (int i = 0; i < N; i++) {
            String op = sc.next();
            if (op.equals("=")) {
                if (sum == -1) {
                    sum = tmp;
                }

                if (sum != tmp) {
                    System.out.println("No");
                    return;
                }

                tmp = sc.nextInt();
            } else {
                tmp += sc.nextInt();
            }
        }
        if (sum != tmp) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}

Python

N = int(input())
values = list(map(eval, input().split("=")))
values.sort()
print("Yes" if values[0] == values[-1] else "No")

C++

#include <iostream>
#include <map>
#include <vector>
using namespace std;

using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  ll N, p, q;
  cin >> N >> p >> q;
  map<int, vector<int>> m;
  rep(i, N) {
    int a, b;
    cin >> a >> b;
    m[-(a * p + b * q)].push_back(i);
  }
  vector<int> rank(N);
  int r = 1;
  for (auto& [_, v] : m) {
    for (auto& i : v) rank[i] = r;
    r += v.size();
  }
  for (auto& x : rank) cout << x << "\n";
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int p = sc.nextInt();
        int q = sc.nextInt();

        TreeMap<Integer, List<Integer>> scores = new TreeMap<Integer, List<Integer>>();
        for (int i = 0; i < N; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            int score = p * a + q * b;
            if (!scores.containsKey(score)) {
                scores.put(score, new ArrayList<Integer>());
            }
            scores.get(score).add(i);
        }

        int[] ranks = new int[N];
        int r = 1;
        for (int score : scores.descendingKeySet()) {
            for (int student : scores.get(score)) {
                ranks[student] = r;
            }
            r += scores.get(score).size();
        }

        StringJoiner sj = new StringJoiner("\n");
        for (int rank : ranks) {
            sj.add(String.valueOf(rank));
        }
        System.out.println(sj.toString());
    }
} 

Python

N, p, q = list(map(int, input().split()))
scores = []
for i in range(N):
    a, b = list(map(int, input().split()))
    scores.append((p * a + q * b, i))
scores.sort(reverse=True)

rank = [-1] * N
rank[scores[0][1]] = 1
for i in range(1, N):
    if scores[i][0] == scores[i-1][0]:
        rank[scores[i][1]] = rank[scores[i-1][1]]
    else:
        rank[scores[i][1]] = i + 1

print(*rank, sep="\n")

C++

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
using namespace std;

mint combi[12][12];

void dfs(int c,long long s,mint v,vector<long long> a,vector<long long> b,map<long long,mint> &mp){
    if(c==a.size()){
        mp[s] += v;
        return;
    }
    
    for(int i=0;i<=10;i++){
        for(int j=0;j<=1;j++){
            dfs(c+1,s+a[c]*i+b[c]*j,v*combi[10][i],a,b,mp);
        }
    }
    
}

int main() {
    
    combi[0][0] = 1;
    for(int i=0;i<10;i++){
        for(int j=0;j<=i;j++){
            combi[i+1][j] += combi[i][j];
            combi[i+1][j+1] += combi[i][j];
        }
    }
    
    int N;
    cin>>N;
    
    vector<long long> a(N/2),b(N/2),c((N+1)/2),d((N+1)/2);
    
    long long sum = 0;
    
    for(int i=0;i<N/2;i++){
        cin>>a[i]>>b[i];
        sum += a[i]*10 + b[i];
    }
    
    for(int i=0;i<(N+1)/2;i++){
        cin>>c[i]>>d[i];
        sum += c[i]*10 + d[i];
    }
    
    if(sum%2==1){
        cout<<0<<endl;
        return 0;
    }
    
    map<long long,mint> ma,mb;
    
    dfs(0,0,1,a,b,ma);
    dfs(0,0,1,c,d,mb);
    
    mint ans = 0;
    
    for(auto x:ma){
        ans += x.second * mb[sum/2-x.first];
    }
    
    cout<<ans.val()<<endl;
    
    return 0;
} 

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        long MOD = 998244353;

        int[] comb = new int[11];
        comb[0] = 1;
        for (int i = 1; i < 11; i++) {
            comb[i] = comb[i-1] * (11-i);
            comb[i] /= i;
        }

        Map<Integer, Map<Long, Long>> dp = new HashMap<Integer, Map<Long, Long>>();
        dp.put(0, new HashMap<Long, Long>() );
        dp.put(1, new HashMap<Long, Long>() );
        for (int i = 0; i < N; i++) {
            Map<Long, Long> ndp = new HashMap<Long, Long>();
            long a = sc.nextLong();
            long b = sc.nextLong();
            for (int j = 0; j <= 10; j++) {
                long t = (2*j - 10) * a;
                for (int k = -1; k <= 1; k++) {
                    if (k == 0) continue;

                    long k1 = t + b * k;
                    long v1 = comb[j];
                    for (long k2 : dp.get(i%2).keySet()) {
                        long pv = ndp.containsKey(k1+k2) ? ndp.get(k1+k2) : 0;
                        long v2 = dp.get(i%2).get(k2);
                        ndp.put(k1+k2, (pv+v1*v2)%MOD);
                    }
                }
            }
            dp.put(i%2, ndp);
        }

        long ans = 0;
        for (long k : dp.get(0).keySet()) {
            if (dp.get(1).containsKey(-k)) {
                ans += dp.get(0).get(k) * dp.get(1).get(-k);
                ans %= MOD;
            }
        }
        System.out.println(ans);
    }
}

Python

from collections import Counter

N = int(input())
MOD = 998244353

comb = [1] * 11
for i in range(1, 11):
    comb[i] = comb[i-1] * (11-i)
    comb[i] //= i

dp = [Counter({0: 1}) for _ in range(2)]
for i in range(N):
    ndp = Counter()
    a, b = list(map(int, input().split()))
    for j in range(11):
        t = (2*j - 10) * a
        for k in [-1, 1]:
            k1 = t + b * k
            v1 = comb[j]
            for k2, v2 in dp[i%2].most_common():
                ndp[k1+k2] += v1 * v2
                ndp[k1+k2] %= MOD

    dp[i%2] = ndp

ans = 0
for k, v in dp[0].most_common():
    ans += v * dp[1][-k]
    ans %= MOD

print(ans)

C++

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

int main() {
  int N, Q;
  cin >> N >> Q;
  vector<int> senbei(N + 1, 0);
  for (int q = 1; q <= Q; q++) {
    int L, R;
    cin >> L >> R;
    for (int j = L; j <= R; j++) senbei[j] ^= 1;
  }
  cout << accumulate(begin(senbei), end(senbei), 0) << endl;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int Q = sc.nextInt();
        int[] reversed = new int[N];
        for (int i = 0; i < Q; i++) {
            int L = sc.nextInt();
            int R = sc.nextInt();

            for (int j = L - 1; j < R; j++) {
                reversed[j] ^= 1;
            }
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            ans += reversed[i];
        }
        System.out.println(ans);
    }
} 

Python

N, Q = list(map(int, input().split()))
is_reversed = [0] * N
for _ in range(Q):
    L, R = list(map(int, input().split()))
    for i in range(L-1, R):
        is_reversed[i] ^= 1

print(sum(is_reversed))

C++

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int n;
  cin >> n;
  vector<pi> pv(3*n);
  for(int i=0;i<3*n;i++){
    cin >> pv[i].first;
    pv[i].second=i+1;
  }
  sort(pv.begin(),pv.end());
  vector<int> res;
  for(int i=n;i<2*n;i++){
    res.push_back(pv[i].second);
  }
  sort(res.begin(),res.end());
  for(auto &nx : res){
    cout << nx << "\n";
  }
  return 0;
} 

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] foods = new int[3*N];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < 3*N; i++) {
            int a = sc.nextInt();
            foods[i] = a;
            map.put(a, i + 1);
        }

        Arrays.sort(foods);
        int[] ans = new int[N];
        for (int i = 0; i < N; i++) {
            ans[i] = map.get(foods[N+i]);
        }
        Arrays.sort(ans);

        StringJoiner sj = new StringJoiner("\n");
        for (int i : ans) {
            sj.add(String.valueOf(i));
        }
        System.out.println(sj.toString());
    }
} 

Python

N = int(input())
A = list(enumerate(map(int, input().split())))
A.sort(key=lambda x: (x[1], x[0]))
print(*[i+1 for i, _ in sorted(A[N:2*N])], sep="\n")

C++

#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;

ll n;
ll a[500005];

int main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];

    ll ans = 0;
    for(int i = 1; i <= n; i++) ans += a[i];

    stack<ll> stk;
    stk.push(-1);
    for(int i = n; i >= 1; i--){
        stk.push(a[i]);
        if(stk.top() == 1){
            for(int j = 1; ; j++){
                if(stk.top() != j) break;
                ans -= j;
                stk.pop();
            }
        }
    }
    cout << ans << endl;

  return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        LinkedList<Integer> A = new LinkedList<Integer>();
        for (int i = 0; i < N; i++) {
            A.add(sc.nextInt());
        }

        LinkedList<Integer> B = new LinkedList<Integer>();
        for (int i = 0; i < N; i++) {
            int a = A.pollLast();
            if (a == 1) {
                int k = 2;
                while (!B.isEmpty() && B.getFirst() == k) {
                    B.pop();
                    k += 1;
                }
            } else {
                B.push(a);
            }
        }

        System.out.println(B.stream().mapToLong(v -> v).sum());
    }
} 

Python

N = int(input())
A = list(map(int, input().split()))
B = []
while A:
    a = A.pop()
    if a == 1:
        k = 2
        while B and B[-1] == k:
            B.pop()
            k += 1
    else:
        B.append(a)

print(sum(B))

C++

#include <iostream>
#include <vector>
using namespace std;

#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;
struct Binomial {
  vector<mint> fac, invfac, inv;
  Binomial(int n) : fac(n + 1), invfac(n + 1), inv(n + 1) {
    fac[0] = invfac[0] = inv[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i;
    invfac[n] = fac[n].inv();
    for (int i = n - 1; i >= 0; i--) {
      invfac[i] = invfac[i + 1] * (i + 1);
      inv[i + 1] = invfac[i + 1] * fac[i];
    }
  }
  mint operator()(int n, int r) {
    if (n < 0 || r < 0 || n < r) return 0;
    return fac[n] * invfac[n - r] * invfac[r];
  }
} C{10000};

#include "atcoder/convolution.hpp"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define sz(v) ((int)(v).size())

vector<mint> add(const vector<mint>& a, const vector<mint>& b) {
  vector<mint> c(max(sz(a), sz(b)));
  rep(i, sz(a)) c[i] += a[i];
  rep(i, sz(b)) c[i] += b[i];
  return c;
}
vector<mint> mul(const vector<mint>& a, const vector<mint>& b) {
  return atcoder::convolution(a, b);
}

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> a(N);
  rep(i, N) cin >> a[i];

  vector g(N, vector<int>{});
  rep(i, N - 1) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    g[A].push_back(B);
    g[B].push_back(A);
  }

  // (i が根の場合の MGF) + 1
  vector<vector<mint>> dp(N);
  {
    auto dfs = [&](auto rc, int c, int p = -1) -> vector<mint> {
      vector<mint> f(K + 1);
      mint buf = 1;
      for (int i = 0; i <= K; i++, buf *= a[c]) f[i] = buf * C.invfac[i];
      for (auto& d : g[c]) {
        if (d == p) continue;
        auto fc = rc(rc, d, c);
        f = mul(f, fc);
        f.resize(K + 1);
      }
      f[0] += 1;
      return dp[c] = f;
    };
    dfs(dfs, 0);
  }

  vector<mint> ans(N);
  vector<mint> I(K + 1);
  I[0] = 1;
  {
    auto dfs = [&](auto rc, int c, int p, vector<mint> dat) -> void {
      vector<mint> f(K + 1);
      mint buf = 1;
      for (int i = 0; i <= K; i++, buf *= a[c]) f[i] = buf * C.invfac[i];

      if (dat.empty()) dat = I;
      f = mul(f, dat);
      f.resize(K + 1);

      vector<int> cid{p};
      vector<vector<mint>> cval{f};
      for (auto& d : g[c]) {
        if (d == p) continue;
        cid.push_back(d);
        cval.push_back(dp[d]);
      }
      vector<vector<mint>> L(sz(cval) + 1), R(sz(cval) + 1);
      L[0] = R.back() = I;
      rep(i, sz(cval)) {
        L[i + 1] = mul(L[i], cval[i]);
        L[i + 1].resize(K + 1);
      }
      for (int i = sz(cval); i--;) {
        R[i] = mul(R[i + 1], cval[i]);
        R[i].resize(K + 1);
      }

      ans[c] = L.back()[K] * C.fac[K];
      int i = 1;
      for (auto& d : g[c]) {
        if (d == p) continue;
        vector<mint> s = mul(L[i], R[i + 1]);
        s.resize(K + 1);
        s[0] += 1;
        rc(rc, d, c, s);
        i++;
      }
    };
    dfs(dfs, 0, -1, {});
  }

  for (auto& x : ans) cout << x.val() << "\n";
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    
    int N;
    cin>>N;
    
    vector<int> b(N);
    for(int i=0;i<N;i++)cin>>b[i];
    
    sort(b.begin(),b.end());
    
    int d = (b[N-1] - b[0])/N;
    
    for(int i=0;i<N;i++){
        if(b[i]+d!=b[i+1]){
            cout<<b[i]+d<<endl;
            return 0;
        }
    }
    
    return 0;
} 

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        long[] B = new long[N];
        long sum = 0;
        for (int i = 0; i < N; i++) {
            B[i] = sc.nextLong();
            sum += B[i];
        }
        Arrays.sort(B);

        System.out.println((B[0]+B[N-1]) * (N+1) / 2 - sum);
    }
}

Python

N = int(input())
B = list(map(int, input().split()))
B.sort()
print((B[0]+B[-1]) * (N+1) // 2 - sum(B))

C++

#include <iostream>
#include <tuple>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

ll w, h, t;
ll sx, sy, tx, ty;
map<ll, ll> mp;

ll check(ll x, ll y, ll rx, ll ry)
{
    x = (x%(2*w)+(2*w)) % (2*w);
    y = (y%(2*h)+(2*h)) % (2*h);
    if(x == rx && y == ry) return 1;
    else return 0;
}

ll calc(ll rx, ll ry)
{
    ll ret = 0;
    for(ll x = -t; x <= t; x++){
        ll r = t*t-x*x;
        if(mp.count(r) == 0) continue;
        ll y = mp[r];
        ret += check(sx+x, sy+y, rx, ry);
        if(y > 0) ret += check(sx+x, sy-y, rx, ry);
    }
    return ret;
}

int main(void)
{
    cin >> w >> h >> t;
    cin >> sx >> sy >> tx >> ty;

    for(ll i = 0; i <= 200000; i++) mp[i*i] = i;

    ll ans = calc(tx, ty);
    ans += calc(2*w-tx, ty);
    ans += calc(2*w-tx, 2*h-ty);
    ans += calc(tx, 2*h-ty);
    cout << ans << endl;

  return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int W = sc.nextInt();
        int H = sc.nextInt();
        long T = sc.nextInt();

        int sx = sc.nextInt();
        int sy = sc.nextInt();
        int tx = sc.nextInt();
        int ty = sc.nextInt();

        int ans = 0;
        for (long dx = -T; dx <= T; dx++) {
            if ((sx + dx + T * 2 * W) % (2 * W) != tx && (sx + dx + T * 2 * W) % (2 * W) != 2 * W - tx) continue;

            long sq_dy = T * T - dx * dx;
            if (sq_dy < 0 || Math.sqrt(sq_dy) % 1 != 0) continue;

            long abs_dy = (long) Math.sqrt(sq_dy);
            if (abs_dy != 0) {
                ans += (sy + abs_dy + T * 2 * H) % (2 * H) == ty ? 1 : 0;
                ans += (sy + abs_dy + T * 2 * H) % (2 * H) == 2 * H - ty ? 1 : 0;
                ans += (sy - abs_dy + T * 2 * H) % (2 * H) == ty ? 1 : 0;
                ans += (sy - abs_dy + T * 2 * H) % (2 * H) == 2 * H - ty ? 1 : 0;
            } else {
                ans += sy % (2 * H) == ty ? 1 : 0;
                ans += sy % (2 * H) == 2 * H - ty ? 1 : 0;
            }
        }
        System.out.println(ans);
    }
}

Python

from math import sqrt


W, H, T = list(map(int, input().split()))
sx, sy = list(map(int, input().split()))
tx, ty = list(map(int, input().split()))

# 総移動距離の2乗 = x方向の移動距離の2乗 + y方向の移動距離の2乗
sq_T = T**2
ans = 0
for dx in range(-T, T+1):
    if (sx + dx) % (2 * W) != tx and (sx + dx) % (2 * W) != 2 * W - tx:
        continue

    sq_dy = sq_T - dx**2
    if sq_dy < 0:
        continue

    abs_dy = sqrt(sq_dy)
    if abs_dy:
        ans += (sy + abs_dy) % (2 * H) == ty
        ans += (sy + abs_dy) % (2 * H) == 2 * H - ty
        ans += (sy - abs_dy) % (2 * H) == ty
        ans += (sy - abs_dy) % (2 * H) == 2 * H - ty
    else:
        ans += sy % (2 * H) == ty
        ans += sy % (2 * H) == 2 * H - ty

print(ans)

C++

#include<bits/stdc++.h>

using namespace std;

int lucas(int n,int r){
  n^=((1<<31)-1);
  if(n&r){return 0;}
  return 1;
}

int main(){
  int n,m;
  cin >> n >> m;
  string s,t;
  cin >> s >> t;
  int k;
  cin >> k;
  vector<int> x(k),y(k);
  for(int i=0;i<k;i++){
    cin >> x[i] >> y[i];
    
    x[i]--;y[i]--;

    if(y[i]==0){
      cout << s[x[i]] << "\n";
    }
    else if(x[i]==0){
      cout << t[y[i]] << "\n";
    }
    else{
      int res=0;
      for(int j=1;j<=x[i];j++){
        if(s[j]=='0'){continue;}
        int d=x[i]-j;
        int r=y[i]-1;
        res+=lucas(d+r,r);
      }
      for(int j=1;j<=y[i];j++){
        if(t[j]=='0'){continue;}
        int d=x[i]-1;
        int r=y[i]-j;
        res+=lucas(d+r,r);
      }
      cout << res%2 << "\n";
    }
  }
  return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        char[] cS = sc.next().toCharArray();
        char[] cT = sc.next().toCharArray();
        int[] S = new int[N];
        int[] T = new int[M];
        for (int i = 0; i < N; i++) S[i] = cS[i] == '1' ? 1 : 0;
        for (int i = 0; i < M; i++) T[i] = cT[i] == '1' ? 1 : 0;

        int K = sc.nextInt();
        for (int i = 0; i < K; i++) {
            int X = sc.nextInt();
            int Y = sc.nextInt();

            if (X == 1) {
                System.out.println(T[Y-1]);
                continue;
            }
            if (Y == 1) {
                System.out.println(S[X-1]);
                continue;
            }

            int xor = 0;
            for (int x = 0; x < X-1; x++) {
                int n = x + Y - 2;
                int k = Y - 2;
                if ((n & k) == k) xor ^= S[X-1-x];
            }

            for (int y = 0; y < Y-1; y++) {
                int n = y + X - 2;
                int k = X - 2;
                if ((n & k) == k) xor ^= T[Y-1-y];
            }

            System.out.println(xor);
        }
    }
}

Python

N, M = list(map(int, input().split()))
S = list(map(int, list(input())))
T = list(map(int, list(input())))

K = int(input())
for _ in range(K):
    X, Y = list(map(int, input().split()))

    if X == 1:
        print(T[Y-1])
        continue
    if Y == 1:
        print(S[X-1])
        continue

    xor = 0
    for x in range(X-1):
        n = x+Y-2
        k = Y-2
        if n&k == k:
            xor ^= S[X-1-x]

    for y in range(Y-1):
        n = y+X-2
        k = X-2
        if n&k == k:
            xor ^= T[Y-1-y]

    print(xor)

C++

#include<bits/stdc++.h>
#define mod 998244353

using namespace std;

vector<long long> subsetConv(int n,vector<long long> &a,vector<long long> &b){
  vector<long long> c(1<<n,0);
  for(int i=0;i<(1<<n);i++){
    for(int j=i;j<(1<<n); ++j |= i){
      c[j]+=a[i]*b[i^j];
      c[j]%=mod;
    }
  }
  return c;
}

int main(){
  int n;
  cin >> n;
  vector<string> s(n);
  for(auto &nx : s){cin >> nx;}

  vector<long long> cnt(n+1,0);
  for(int lim=0;lim<=n;lim++){
    vector<long long> f(1<<n,0);
    f[0]=1;
    for(int i=0;i<n;i++){
      int fl=0;
      for(int j=0;j<n;j++){
        if(s[i][j]=='.'){fl|=(1<<j);}
      }
      vector<long long> g(1<<n,0);
      for(int j=0;j<(1<<n);j++){
        if((j|fl)!=fl){continue;}
        if(__builtin_popcount(j)>lim){continue;}
        g[j]++;
      }
      f=subsetConv(n,f,g);
    }
    for(auto &nx : f){
      cnt[lim]+=nx;
      cnt[lim]%=mod;
    }
  }

  long long res=0;
  for(long long i=1;i<=n;i++){
    res+=i*(mod+cnt[i]-cnt[i-1]);
    res%=mod;
  }
  cout << res << "\n";
  return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long MOD = 998244353;
        int N = sc.nextInt();
        int M = 1<<N;
        long[][] dp = new long[M][N+1];
        dp[0][0] = 1;

        for (int n = 0; n < N; n++) {
            long[][] ndp = new long[M][N+1];
            char[] S = sc.next().toCharArray();
            for (int i = 0; i < M; i++) {
                List<Integer> lst = new ArrayList<Integer>();
                for (int j = 0; j < N; j++) {
                    if (!((i>>j&1) == 1 || S[j] == '#')) lst.add(j);
                }

                for (int j = 0; j < 1<<lst.size(); j++) {
                    int put = 0;
                    int cnt = 0;
                    for (int k = 0; k < lst.size(); k++) {
                        if ((j>>k&1) == 1) {
                            put |= 1<<lst.get(k);
                            cnt += 1;
                        }
                    }
                    int s = i|put;
                    for (int k = 0; k < N+1; k++) {
                        ndp[s][Math.max(cnt, k)] += dp[i][k];
                        if (MOD <= ndp[s][Math.max(cnt, k)]) ndp[s][Math.max(cnt, k)] -= MOD;
                    }
                }
            }
            dp = ndp;
        }

        long ans = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 1; j < N+1; j++) {
                ans += dp[i][j] * j;
                ans %= MOD;
            }
        }

        System.out.println(ans);
    }
} 

Python

mod = 998244353
def subset_conv(n, a, b):
    c = [0] * (1<<n)
    for i in range(1<<n):
        j = i
        while j < 1<<n:
            c[j] += a[i] * b[i^j]
            c[j] %= mod
            j += 1
            j |= i

    return c

def main():
    N = int(input())
    S = [input() for _ in range(N)]

    cnt = [0] * (N+1)
    for lim in range(N+1):
        f = [0] * (1<<N)
        f[0] = 1
        for i in range(N):
            fl = 0
            for j in range(N):
                if S[i][j] == '.': fl |= 1<<j

            g = [0] * (1<<N)
            for j in range(1<<N):
                if j|fl != fl: continue
                if bin(j).count("1") >lim: continue
                g[j] += 1
            f = subset_conv(N, f, g)

        for nx in f:
            cnt[lim] += nx
            cnt[lim] %= mod

    res = 0
    for i in range(1, N+1):
        res += i * (mod+cnt[i]-cnt[i-1])
        res %= mod
    print(res)

if __name__ == '__main__':
    main()