Chayas
Source: aizu

Chayas

Once upon a time, there were a number of chayas (teahouses) along one side of an east-west road in Yokohama. Although the total number of chayas is known, the information about their locations was considered to be lost totally.

Recently, a document describing the old townscapes of Yokohama has been found. The document contains a number of records on the order of the locations of chayas. Each record has information below on the order of the locations of three chayas, say $a$, $b$, and $c$.

Chaya $b$ was located between chayas $a$ and $c$. Note that there may have been other chayas between $a$ and $b$, or between $b$ and $c$. Also, note that chaya $a$ may have been located east of $c$ or west of $c$.

We want to know how many different orders of chayas along the road are consistent with all of these records in the recently found document. Note that, as the records may have some errors, there might exist no orders consistent with the records.

Input

The input consists of a single test case given in the following format.

$n$ $m$
$a_1$ $b_1$ $c_1$
.
.
.
$a_m$ $b_m$ $c_m$


Here, $n$ represents the number of chayas and m represents the number of records in the recently found document. $3 \leq n \leq 24$ and $1 \leq m \leq n \times (n - 1) \times (n - 2)/2$ hold. The chayas are numbered from $1$ to $n$.

Each of the following $m$ lines represents a record. The $i$-th of them contains three distinct integers $a_i$, $b_i$, and $c_i$, each between $1$ and $n$, inclusive. This says that chaya $b_i$ was located between chayas $a_i$ and $c_i$. No two records have the same information, that is, for any two different integers $i$ and $j$, the triple ($a_i$, $b_i$, $c_i$) is not equal to ($a_j, b_j, c_j$) nor ($c_j, b_j, a_j$).

Output

Output the number of different orders of the chayas, from east to west, consistent with all of the records modulo $998 244 353$ in a line. Note that $998 244 353 = 2^{23} \times 7 \times 17 + 1$ is a prime number.

Sample Input 1
5 4
1 2 4
2 3 5
3 2 4
1 3 2

Sample Output 1
4

Sample Input 2
4 2
3 1 4
1 4 3

Sample Output 2
0


For Sample Input 1, four orders, (1, 5, 3, 2, 4), (4, 2, 3, 1, 5), (4, 2, 3, 5, 1), and (5, 1, 3, 2, 4), are consistent with the records.

For Sample Input 2, there are no consistent orders.

C++ solution:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define rep(i,n) for(ll i=0;i<ll(n);i++)
#define all(A) A.begin(),A.end()

vll dx = { 1,0,-1,0 };
vll dy = { 0,1,0,-1 };

const ll mod=998244353;
int main() {

    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    ll N,M;
    cin>>N>>M;
    vector<vector<pair<ll,ll>>> D(N);
    rep(i,M){
        ll A,B,C;
        cin>>A>>B>>C;
        A--;B--;C--;
        D[B].push_back({A,C});
    }
    vll DP(1<<N,0);
    DP[0]=1;
    rep(bit,1<<N){
        if(DP[bit]==0)continue;
        rep(n,N){
            if(bit&(1<<n))continue;
            ll nbit=bit+(1<<n);
            bool OK=1;
            for(auto [a,c]:D[n]){
                ll d=bit&(1<<a);
                ll e=bit&(1<<c);
                if((d>0&&e>0)||(d+e==0)){
                    OK=0;
                    break;
                }
            }
            if(OK){
                DP[nbit]+=DP[bit];
                if(DP[nbit]>=mod)DP[nbit]-=mod;
            }
        }
    }
    cout<<DP[(1<<N)-1]<<endl;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

const mod = 998244353

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	scanner.Scan()
	N, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	M, _ := strconv.Atoi(scanner.Text())

	ng := make([][][2]int, N)
	for i := 0; i < M; i++ {
		scanner.Scan()
		a, _ := strconv.Atoi(scanner.Text())
		scanner.Scan()
		b, _ := strconv.Atoi(scanner.Text())
		scanner.Scan()
		c, _ := strconv.Atoi(scanner.Text())
		a--
		b--
		c--
		ng[b] = append(ng[b], [2]int{1 << a, 1 << c})
	}

	ok := make([]int, 1<<N)
	ok[0] = 1

	for mask := 0; mask < (1 << N); mask++ {
		if ok[mask] == 0 {
			continue
		}
		for b := 0; b < N; b++ {
			if mask&(1<<b) != 0 {
				continue
			}
			valid := true
			for _, pair := range ng[b] {
				aMask, cMask := pair[0], pair[1]
				aIn := (mask & aMask) != 0
				cIn := (mask & cMask) != 0
				if (aIn && cIn) || (!aIn && !cIn) {
					valid = false
					break
				}
			}
			if valid {
				newMask := mask | (1 << b)
				ok[newMask] = (ok[newMask] + ok[mask]) % mod
			}
		}
	}

	fmt.Println(ok[(1<<N)-1])
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 998244353;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        List<List<int[]>> constraints = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            constraints.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            constraints.get(b).add(new int[]{1 << a, 1 << c});
        }

        int[] dp = new int[1 << N];
        dp[0] = 1;

        for (int mask = 0; mask < (1 << N); mask++) {
            if (dp[mask] == 0) continue;
            for (int b = 0; b < N; b++) {
                if ((mask & (1 << b)) != 0) continue;
                boolean valid = true;
                for (int[] constraint : constraints.get(b)) {
                    int aMask = constraint[0];
                    int cMask = constraint[1];
                    boolean aIn = (mask & aMask) != 0;
                    boolean cIn = (mask & cMask) != 0;
                    if ((aIn && cIn) || (!aIn && !cIn)) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    int newMask = mask | (1 << b);
                    dp[newMask] = (dp[newMask] + dp[mask]) % MOD;
                }
            }
        }

        System.out.println(dp[(1 << N) - 1]);
    }
}

JavaScript solution:
const mod = 998244353;

function main() {
    const input = require('fs').readFileSync(0, 'utf-8').trim().split('\n');
    const firstLine = input[0].trim().split(' ').map(Number);
    const N = firstLine[0];
    const M = firstLine[1];
    const constraints = [];
    for (let i = 1; i <= M; i++) {
        const parts = input[i].trim().split(' ').map(Number);
        constraints.push([parts[0] - 1, parts[1] - 1, parts[2] - 1]);
    }

    // Preprocess constraints for each b
    const ng = Array.from({ length: N }, () => []);
    for (const [a, b, c] of constraints) {
        ng[b].push([1 << a, 1 << c]);
    }

    const dp = new Array(1 << N).fill(0);
    dp[0] = 1;

    for (let mask = 0; mask < (1 << N); mask++) {
        if (dp[mask] === 0) continue;
        for (let b = 0; b < N; b++) {
            if (mask & (1 << b)) continue;
            let valid = true;
            for (const [aMask, cMask] of ng[b]) {
                const hasA = (mask & aMask) !== 0;
                const hasC = (mask & cMask) !== 0;
                if ((hasA && hasC) || (!hasA && !hasC)) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                const newMask = mask | (1 << b);
                dp[newMask] = (dp[newMask] + dp[mask]) % mod;
            }
        }
    }

    console.log(dp[(1 << N) - 1]);
}

main();

Python solution:
import sys
def input(): return sys.stdin.readline().rstrip()
mod = 998244353
N, M = map(int, input().split())
L = [[~-int(i) for i in input().split()] for _ in range(M)]
ng = [[] for _ in range(N)]
for a, b, c in L:
    ng[b].append((1<<a, 1<<c))
ok = [0]*(1<<N)
ok[0] = 1

for i in range(1<<N):
    if not ok[i]:
        continue
    for b in range(N):
        if i&(1<<b):
            continue
        x = 1
        for a, c in ng[b]:
            if (i&a and i&c) or not (i&a or i&c):
                x = 0
                break
        if x:
            ok[i|(1<<b)] += ok[i]
            ok[i|(1<<b)] %= mod
print(ok[-1])

Ruby solution:
require 'set'

MOD = 998244353

def solve
  input = gets.chomp.split
  n = input[0].to_i
  m = input[1].to_i

  constraints = Array.new(n) { [] }
  m.times do
    a, b, c = gets.chomp.split.map(&:to_i)
    a -= 1
    b -= 1
    c -= 1
    constraints[b] << [1 << a, 1 << c]
  end

  dp = Array.new(1 << n, 0)
  dp[0] = 1

  (0...1 << n).each do |mask|
    next if dp[mask] == 0

    n.times do |b|
      next if mask & (1 << b) != 0

      valid = true
      constraints[b].each do |a_mask, c_mask|
        a_in = (mask & a_mask) != 0
        c_in = (mask & c_mask) != 0
        unless (a_in || c_in) && !(a_in && c_in)
          valid = false
          break
        end
      end

      if valid
        new_mask = mask | (1 << b)
        dp[new_mask] = (dp[new_mask] + dp[mask]) % MOD
      end
    end
  end

  puts dp[(1 << n) - 1]
end

solve