#P12567. [集训队互测 2024day11]往日之影

    ID: 11730 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700数学组合数学生成函数模运算数论多项式概率论

[集训队互测 2024day11]往日之影

2023 年 ? 月 ? 日。

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

“这是,不属于我的记忆?”

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

题目大意

一个简单图有 nn 个顶点,每对不同顶点之间有 12\frac{1}{2} 概率连边,12\frac{1}{2} 概率不连边(概率独立),给定数组 cc,求使得每一个顶点 uu,在形成的图中度数都  mod 4=cu\bmod 4=c_u 的概率。

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

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

本题多测。

保证模数是奇素数。

输入格式

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

接下来 TT 组数据。

对于第 ii 组数据,先输入一行一个整数 nin_i 表示图的点数。接下来一行四个整数 aia_i 含义同题面。

输出格式

对于每组数据,输出一行一个整数,表示概率在  mod p\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
982646785
997574145
398756258
930951642

样例解释

对于第一组,有理数表示为 00。

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

对于第三组,有理数表示为 1116384\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≤7T=1,n\le 7

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

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

Subtask 4 (10pts) : a0=n,a1=a2=a3=0a_0=n,a_1=a_2=a_3=0。

Subtask 5 (50pts) : T≤105,∑n≤106T\le 10^5,\sum n\le 10^6