【题解】排列计数

题目描述求有多少种 1 到 n 的排列 a,满足序列恰好有 m 个位置 i,使得 ai=ia_i = iai​=i。答案对 109+710^9 + 7109+7 取模。输入格式本题单测试点内有多组数据。输入的第一行是一个整数 T,代表测试数据的整数。以下 T 行,每行描述一组测试数据。对于每组测试数


乘法逆元

定义ax≡1 mod pa x \equiv 1\ mod \ pax≡1 mod p这里xxx就是aaa的逆元。一个数有逆元的充分必要条件是gcd(a,p)=1,此时逆元唯一存在。求解逆元的方式拓展欧几里若m不为质数,可以使用拓展欧几里得求逆元根据裴蜀定理,若gcd(a,b)=1则gcd是a,b两


【题解】乘法逆元2

题目描述给定 n 个正整数 aia_iai​ ,求它们在模 p 意义下的乘法逆元。由于输出太多不好,所以将会给定常数 k,你要输出的答案为:∑i=1nkiai\sum\limits_{i=1}^n\frac{k^i}{a_i}i=1∑n​ai​ki​答案对 p 取模。输入格式第一行三个正整数 n,p


【题解】越狱

监狱有 n 个房间,每个房间关押一个犯人,有 m 种宗教,每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱。