#1805. 往日之影
往日之影
往日之影
题目描述
标题: 往日之影 - Problem - QOJ.ac
#7838. 往日之影
The problem was used in the following contests:
2023 年 ? 月 ? 日。
⟦求完全图有多少个每个顶点度均为偶数的子图?⟧
“这是,不属于我的记忆?”
现在,你需要快速解决这样一道熟悉的问题..........
题目大意
一个简单图有 n 个顶点,每对不同顶点之间有 12 概率连边,12 概率不连边(概率独立),给定数组 c,求使得每一个顶点 u,在形成的图中度数都 mod4=cu 的概率。
由于点之间没有顺序区别,为了减少输入量,给出 a0,a1,a2,a3,ai:=∑j=1n[cj=i]。
换句话说,你可以认为 u∈[1,a0] 的 cu=0,u∈[a0+1,a0+a1] 的 cu=1,u∈[a0+a1+1,a0+a1+a2] 的 cu=2,u∈[a0+a1+a2+1,n] 的 cu=3。
本题多测。
保证模数是奇素数。
输入格式
一行两个整数 T,p 分别表示数据组数和模数。
接下来 T 组数据。
对于第 i 组数据,先输入一行一个整数 ni 表示图的点数。接下来一行四个整数 ai 含义同题面。
输出格式
对于每组数据,输出一行一个整数,表示概率在 modp 意义下的值。
样例输入
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
样例解释
对于第一组,有理数表示为 0。
对于第二组,有理数表示为 164。
对于第三组,有理数表示为 1116384
数据范围
全体数据保证 T≤105,∑n≤106,p∈P,p≠2,2|∑i=03aii。
Subtask 1 (10pts) : T=1,n≤7
Subtask 2 (20pts) : ∑n≤40,p=998244353
Subtask 3 (10pts) : ∑n≤100,p=998244353
Subtask 4 (10pts) : a0=n,a1=a2=a3=0。
Subtask 5 (50pts) : T≤105,∑n≤106
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
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