往日之影 - Problem

2023 年 ? 月 ? 日。

⟦求完全图有多少个每个顶点度均为偶数的子图？⟧

“这是，不属于我的记忆？”

现在，你需要快速解决这样一道熟悉的问题..........

题目大意

一个简单图有 $ n $ 个顶点，每对不同顶点之间有 $ \frac{1}{2} $ 概率连边，$ \frac{1}{2} $ 概率不连边（概率独立），给定数组 $ c $，求使得每一个顶点 $ u $，在形成的图中度数都 $ \bmod 4=c_u $ 的概率。

由于点之间没有顺序区别，为了减少输入量，给出 $ a_0,a_1,a_2,a_3 $，$ a_i:=\sum\limits_{j=1}^n[c_j=i] $。

换句话说，你可以认为 $ u\in [1,a_0] $ 的 $ c_u=0 $，$ u\in [a_0+1,a_0+a_1] $ 的 $ c_u=1 $，$ u\in[a_0+a_1+1,a_0+a_1+a_2] $ 的 $ c_u=2 $，$ u\in [a_0+a_1+a_2+1,n] $ 的 $ c_u=3 $。

本题多测。

保证模数是奇素数。

输入格式

一行两个整数 $ T,p $ 分别表示数据组数和模数。

接下来 $ T $ 组数据。

对于第 $ i $ 组数据，先输入一行一个整数 $ n_i $ 表示图的点数。接下来一行四个整数 $ a_i $ 含义同题面。

输出格式

对于每组数据，输出一行一个整数，表示概率在 $ \bmod p $ 意义下的值。

样例输入

5 998244353
4
2 0 2 0
4
0 3 0 1
6
6 0 0 0
40
10 5 18 7
100
30 11 30 29

样例输出

样例解释

对于第一组，有理数表示为 $ 0 $。

对于第二组，有理数表示为 $ \frac{1}{64} $。

对于第三组，有理数表示为 $ \frac{11}{16384} $

数据范围

全体数据保证 $ T\le 10^5,\sum n\le 10^6,p\in \mathbb{P},p\not=2,2|\sum\limits_{i=0}^3 a_i i $。

Subtask 1 (10pts) : $ T=1,n\le 7 $

Subtask 2 (20pts) : $ \sum n\le 40,p=998244353 $

Subtask 3 (10pts) : $ \sum n\le 100,p=998244353 $

Subtask 4 (10pts) : $ a_0=n,a_1=a_2=a_3=0 $。

Subtask 5 (50pts) : $ T\le 10^5,\sum n\le 10^6 $

QOJ.ac

QOJ