Uva 11174 Stand in a Line 문제 풀이 보고서(증분 + 역원)
1521 단어 점차 미루다
코드는 다음과 같습니다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
typedef long long LL;
int powMod(LL a, int b)
{
LL res = 1;
while(b)
{
if(b&1)
res = res*a%mod;
b>>=1;
a = a*a%mod;
}
return (int)res;
}
int inv(int n)
{
return powMod(n, mod-2);
}
const int maxn = 40010;
int first[maxn],nxt[maxn],vv[maxn];
bool isSon[maxn];
int factorial[maxn];
LL ans;
void init()
{
factorial[0] = 1;
for(int i=1;i<maxn;i++)
factorial[i] = (long long)factorial[i-1]*i%mod;
}
int dfsTree(int n,int p=0)
{
int sonNum=1;
for(int e=first[n];e;e=nxt[e])
sonNum+=dfsTree(vv[e],n);
if(sonNum>1) ans = ans*inv(sonNum)%mod;
return sonNum;
}
void work()
{
int n,m;
scanf("%d%d",&n,&m);
ans = factorial[n];
int e = 2;
memset(first, 0, sizeof(first));
memset(isSon, 0, sizeof(isSon));
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
nxt[e] = first[v], vv[e] = u, first[v] = e++;
isSon[u] = true;
}
for(int i=1;i<=n;i++) if(!isSon[i])
dfsTree(i);
printf("%d
", (int)ans);
}
int main()
{
init();
int T;
scanf("%d", &T);
while(T--)
work();
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
P1722 매트릭스 II & P1044 창고 문제풀이블로그 원제 링크 1 1 1 1 1 원제 링크 2, 2, 2. 먼저 P1722\text{P1722} P1722를 살펴보겠습니다. 제목 요약: 하나 있다× n 2\times n 2×n의 격자, 현재 너는 그것들의 모든...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
