Ambulance

NC54733. Ambulance

描述

Xu1024 is a boy who is responsible for fixing the bug of HOJ.

Because the Hunan university ACM freshman competition is coming, Xu1024 find that HOJ still has a lot of functions not realized. To solve this problem, Xu1024 had to work a 996 schedule.

Unfortunately, Xu1024 was carried into the ambulance because of exhaustion. More unfortunate thing happened, There is something wrong with the ambulance's electrical system. The electrical system of the ambulance is very special. There are N wires in system A and N wires in system B, and the ambulance can restart when any i-th wire in system A is connected to line the Ai-th wire in system B. The A1,A2,...An is a premutation of n.
In order to save the child, you decide to reconnect the electric wire so that every wire in system B will be connected with a unique line in system A. How many ways can the ambulance restart? Due to the answer will be very large, you only need to output the answer mod 1,000,000,007.

输入描述

The first line contains one integer N（N ≤100000）, the number of the system’s wire(s).
The next line contains N integers, the i-th number is Ai.
It is guaranteed that  A1,A2,...An is a permutation of n.

输出描述

Output an integer which denotes the answer.

示例1

输入:

2
1 2

输出:

说明:

There two ways to connect the electric wire.

One is choose the 1st A wire to connect the 1st B wire and choose the 2nd A wire to connect the 2nd B wire.

Another is choose the 2nd A wire to connect the 1st B wire and choose the 1st A wire to connect the 2nd B wire.

Only the first way can restart the ambulance.

示例2

输入:

3
2 3 1

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 760K, 提交时间: 2020-01-11 13:35:51

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int MD=1e9+7;
int f[N],n;
int main() {
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%*d");
	f[0]=0,f[1]=1;
	for(int i=2;i<=n;i++) {
		f[i]=1LL*(f[i-1]+f[i-2])*(i-1)%MD;
	}
	printf("%d\n",f[n]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 1244K, 提交时间: 2020-02-25 14:57:01

#include<bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
int main()
{
	int n;
	string s;
	cin>>n;
	long long a[n+5];
	getline(cin,s);
	a[0]=0,a[1]=1;
	for(int i=2;i<=n;i++)
	a[i]=(i-1)*(a[i-1]+a[i-2])%Mod;
	cout<<a[n]<<"\n";
	return 0;
}

上一题

下一题

详情