#1805. 往日之影

    ID: 1805 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1431来源:qoj.ac数据:公开样例组合数学概率期望

往日之影

往日之影

题目描述

标题: 往日之影 - Problem - QOJ.ac

#7838. 往日之影

Statistics

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