题目大意:村子里有n个村名民,现在他们要排成一列,处于对长辈的尊敬,他们不能排在自己父亲的前面,有些人的父亲不一定在村子了。问有多少种列的顺序。
解题思路:【算法竞赛入门经典-训练指南】的例题,主要还用到了欧几里得拓展定理求逆元。
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 40005;
const ll MOD = 1e9+7;
int n, m;
ll v[N];
vector<int> g[N];
void init () {
scanf("%d%d", &n, &m);
memset(v, 0, sizeof(v));
for (int i = 0; i <= n; i++)
g[i].clear();
int a, b;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
g[b].push_back(a);
}
}
ll dfs(int x) {
if (v[x])
return v[x];
for (int i = 0; i < g[x].size(); i++)
v[x] += dfs(g[x][i]);
return ++v[x];
}
void gcd (ll a, ll b, ll& x, ll& y, ll& d) {
if (b == 0) {
d = a;
x = 1;
y = 0;
} else {
gcd(b, a%b, y, x, d);
y -= x*(a/b);
}
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init ();
ll ans = 1, b = 1;
for (ll i = 1; i <= n; i++)
ans = (ans * i) % MOD;
for (int i = 1; i <= n; i++)
b = (b * dfs(i)) % MOD;
ll p, k, d = 1;
gcd(b, MOD, p, k, d);
ans = ((ans * p) % MOD + MOD) % MOD;
printf("%lld\n", ans);
}
return 0;
}
分享到:
相关推荐
组合数学- 组合数取模- 逆元与递推打表.rar
c/c++相关代码(cpp),乘法逆元有关模板整合(附有注释),顺便整合了了阶乘逆元,以及排列组合计算和Lucas的模板代码。
算法-数论- 逆元.rar
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
证明了C 代数A中的元素A是可逆的充要条件是存在两个非负实数λ1和λ2,且λ1≠λ2以及酉群中的两个元素U1和U2使得A=λ1U1+λ2U2,给出了C 代数A中范数不大于1的可逆元的全体闭包和酉群的一些关系.
算法-数论- 逆元与同余式定理.rar
群判定,逆元,元素的阶 #include using namespace std; #define N 10000 //对四元群运算函数的定义 char ysuan(char a,char b) { char arr[4]={'a','b','c','e'}; int i=0,j=0; if(a==b) { return arr[3]; }...
本程序可进行仿射加密和求解逆元的操作。 1-仿射加密,2-求逆元
扩展欧几里得算法求逆元
简单讲解用辗转相除法计算乘法逆元,用于密码学加密,附C语言实现算法(对正整数运算)
算法-乘法逆元(洛谷-P3811)(包含源程序).rar
Matlab,扩展欧几里德算法,求模b条件下,a的乘法逆元,函数Eulid.m,直接调用传入参数就可以用,含参数使用注释。
网络安全课程上机作业,用matlab编写的求解乘法逆元代码,如果有什么问题请留言。
试试吧!对于很多一直邱乘法逆元函数的人来说是一个非常好的选择
用C语言简单实现乘法逆元计算的代码(!只能计算正整数)
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
加密解密的基础,扩展欧几里得算法(辗转相除法)
关于 线性求逆元 算法的代码,自己写的,和大家分享,希望大家能多多指教
用递归实现的求逆元的代码,使用中的算法是扩展的欧几里得算法。输入本元和模数,得到乘法逆元。
用c语言实现逆元的计算,通过自己设计算法代码实现。