#P12027. [2024年联测]挑战 NPC X

[2024年联测]挑战 NPC X

题目描述

给定 nn 个 1,2,⋯n1,2,\cdots n 的排列 a1,a2,⋯ana_1,a_2,\cdots a_n,记 f(S)f(S) 为满足下列条件的 nn 元组 (b1,b2,⋯bn)(b_1,b_2,\cdots b_n) 个数:

  • bb 为一个 1,2,⋯n1,2,\cdots n 的排列
  • b_i=i$ 或排列 $a_i$ 中,数 $b_i$ 在数 $i$ 之前

qq 组询问,每次给定一个集合 SS,求 f(S)f(S)。

输入格式

第一行一个正整数 nn。

后面 nn 行,其中第 ii 行 nn 个正整数 ai,1,ai,2,⋯ai,na_{i,1},a_{i,2},\cdots a_{i,n},表示排列 aia_i。

后面一行一个正整数 qq。

此后 qq 行,每行一个长度为 nn,字符集为 {0,1}\{0,1\} 的字符串 TT,表示一组询问。其中 i∈Si\isin S 当且仅当 TT 第 ii 位为1。不保证 SS 非空。

输出格式

对于每个询问,输出一行一个非负整数,表示答案。

样例

ex_npc1.in
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
1111
1100
0101
1000
0110
ex_npc1.out
2
1
1
2
2

ex_npc2.in/out 见下发文件。

数据范围

对于所有测试点,满足 3≤n≤183 \le n \le 18, 1≤q≤2∗1051 \le q \le 2*10^5, aia_i 为一个 1,2,⋯n1,2,\cdots n 的排列。

以下 idid 为测试点编号。

测试点 n≤n\le qi≤q_i\le
1∽151\backsim 15 id+2id+2 id∗104id*10^4
16∽2016\backsim 20 1818 (id−15)∗4∗104(id-15)*4*10^4

提示:答案显然不超过 n!n!