Category Archives: HDOJ

HDOJ 1159-Common Subsequence

HDOJ 1159-Common Subsequence
Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 38564 Accepted Submission(s): 17705
Problem Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
Source
Southeastern Europe 2003


求最长公共子序列。DP模板题,使用一个dp数组即可,用pre记录原来左上角的值。
代码如下,如果要求出一个lcs,参考《算法导论》P225,使用一个二维数组direction记录每个格子最大值来自哪个方向,重构lcs时从右下角不停的往前找。

#include<string>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int lcs(const string &a, const string &b) {
	int n = a.size(), m = b.size();
	if (n == 0 || m == 0)return 0;
	vector<int> dp(m + 1, 0);
	for (int i = 1; i <= n; ++i) {
		int pre = 0;
		for (int j = 1; j <= m; ++j) {
			int cur = 0;
			if (a[i - 1] == b[j - 1])cur = pre + 1;
			else cur = max(dp[j - 1], dp[j]);
			pre = dp[j];
			dp[j] = cur;
		}
	}
	return dp[m]; // 最大值就是右下角的值
}
void construct_lcs(vector<vector<int>> &direction, const string &a, int i, int j, string &lcs) {
	if (i == 0 || j == 0)return;
	if (direction[i][j] == 3) {
		construct_lcs(direction, a, i - 1, j - 1, lcs);
		lcs += string(1, a[i - 1]); // direction下标1对应a下标0,所以i-1
	}
	else if (direction[i][j] == 2) {
		construct_lcs(direction, a, i - 1, j, lcs);
	}
	else {
		construct_lcs(direction, a, i, j - 1, lcs);
	}
}
string lcs_string(const string &a, const string &b) {
	int n = a.size(), m = b.size();
	if (n == 0 || m == 0)return 0;
	vector<int> dp(m + 1, 0);
	vector<vector<int>> direction(n + 1, vector<int>(m + 1, 0)); // 1:left,2:up,3:diagonal
	for (int i = 1; i <= n; ++i) {
		int pre = 0;
		for (int j = 1; j <= m; ++j) {
			int cur = 0;
			if (a[i - 1] == b[j - 1]) {
				cur = pre + 1;
				direction[i][j] = 3;
			}
			else {
				if (dp[j - 1] > dp[j]) {
					cur = dp[j - 1];
					direction[i][j] = 1;
				}
				else {
					cur = dp[j];
					direction[i][j] = 2;
				}
			}
			pre = dp[j];
			dp[j] = cur;
		}
	}
	string ans;
	construct_lcs(direction, a, n, m, ans); // 从右下角递归往前找,LCRS P225
	return ans;
}
int main() {
	//freopen("input.txt", "r", stdin);
	string a, b;
	while (cin >> a >> b) {
		cout << lcs(a, b) << endl;
		//cout << lcs(a, b) << "\t" << lcs_string(a, b) << endl;;
	}
	return 0;
}

本代码提交AC,用时46MS。

HDOJ 5424-Rikka with Graph II

HDOJ 5424-Rikka with Graph II
Rikka with Graph II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 379 Accepted Submission(s): 94
Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has a non-direct graph with n vertices and n edges. Now he wants you to tell him if there exist a Hamiltonian path.
It is too difficult for Rikka. Can you help her?
Input
There are no more than 100 testcases.
For each testcase, the first line contains a number n(1≤n≤1000).
Then n lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v.
Output
For each testcase, if there exist a Hamiltonian path print "YES" , otherwise print "NO".
Sample Input
4
1 1
1 2
2 3
2 4
3
1 2
2 3
3 1
Sample Output
NO
YES
Hint
For the second testcase, One of the path is 1->2->3
If you doesn't know what is Hamiltonian path, click here (https://en.wikipedia.org/wiki/Hamiltonian_path).
Source
BestCoder Round #53 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422


这题题意很明确,判断一个无向图中是否存在哈密顿路径,注意不是哈密顿回路。

由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次,形成的路径称为哈密顿路径,闭合的哈密顿路径称作哈密顿回路,含有哈密顿回路的图称为哈密顿图。

本来判断一个常规图中是否存在哈密顿路径是NP完全问题,不可能有多项式解,所以如果依次对每个点DFS,肯定超时。
但是这题很特殊,图中只有n个点,n条边!如果存在哈密顿路径L,则路径长度为n-1条边,设L两个端点为A,B,此时还剩下一条边a,这条边有三种情况:
1)a在L的内部连接,这时A,B的度数都为1,其他点的度数为2或3;
2)a一端在A(或B),另一端在L的内部,这时L的另一个端点B(或A)的度数为1,其他点的度数为2或3;
3)a连接了A,B,此时所有点的度数都为2。
如果存在哈密顿路径,这三种情况下,L的某个端点的度数都是最少的。所以可以先找到度数最小的点,再从这个点开始DFS,这样只需要一次DFS就可以判断是否存在哈密顿路径。
当然要先判断这个图是否连通,我起初使用了并查集,但是超时,郁闷。后来发现,如果哈密顿路径存在,则肯定连通,且此时读数为1点不超过2个,所以可以用这个条件判断是否连通。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
const int kMaxN = 1005;
int degree[kMaxN];
vector<vector<int>> path;
int visit[kMaxN];
int n, done;
bool DFS(int s)
{
	done++;
	visit[s] = 1;
	if (done == n)
		return true;
	int v;
	for (int i = 0; i < path[s].size(); i++)
	{
		v = path[s][i];
		if (!visit[v])
		{
			if (DFS(v))
				return true;
		}
	}
	done--;
	visit[s] = 0;
	return false;
}
bool CheckHamiltonian()
{
	int min_degree = n + 1, bad_node_num = 0, id;
	for (int i = 1; i <= n; i++)
	{
		if (degree[i] && degree[i] < min_degree)
		{
			min_degree = degree[i];
			id = i;
		}
		if (degree[i] <= 1)
			bad_node_num++;
	}
	if (bad_node_num > 2)
		return false;
	memset(visit, 0, sizeof(visit));
	done = 0;
	return DFS(id);
}
int main()
{
	//freopen("input.txt", "r", stdin);
	while (~scanf("%d", &n))
	{
		memset(degree, 0, sizeof(degree));
		path.clear();
		path.resize(n + 1);
		int u, v;
		for (int i = 0; i < n; i++)
		{
			scanf("%d %d", &u, &v);
			if (u == v)
				continue;
			degree[u]++;
			degree[v]++;
			path[u].push_back(v);
			path[v].push_back(u);
		}
		if (CheckHamiltonian())
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

本代码提交AC,用时93MS,内存1800K。

HDOJ 5422-Rikka with Graph

HDOJ 5422-Rikka with Graph
Rikka with Graph
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 144 Accepted Submission(s): 72
Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has a non-direct graph with n vertices and m edges. The length of each edge is 1. Now he wants to add exactly an edge which connects two different vertices and minimize the length of the shortest path between vertice 1 and vertice n. Now he wants to know the minimal length of the shortest path and the number of the ways of adding this edge.
It is too difficult for Rikka. Can you help her?
Input
There are no more than 100 testcases.
For each testcase, the first line contains two numbers n,m(2≤n≤100,0≤m≤100).
Then m lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v. There may be multiedges and self loops.
Output
For each testcase, print a single line contains two numbers: The length of the shortest path between vertice 1 and vertice n and the number of the ways of adding this edge.
Sample Input
2 1
1 2
Sample Output
1 1
Hint
You can only add an edge between 1 and 2.
Source
BestCoder Round #53 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422


水题。
如果原来就有边(1,n),则最短距离就是1,可以任选2个点构成一条新边,方案数C^2_n;如果原来没有边(1,n),则添加的新边就是(1,n),最短距离还是1,此时只有一种方案。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int main()
{
	int n, m;
	while (~scanf("%d %d", &n, &m))
	{
		bool connected = false;
		int u, v;
		while (m--)
		{
			scanf("%d %d", &u, &v);
			if ((u == 1 && v == n) || (u == n&&v == 1))
				connected = true;
		}
		if (connected)
			printf("1 %d\n", n*(n - 1) / 2);
		else
			printf("1 1\n");
	}
	return 0;
}

本代码提交AC,用时0MS,内存1216K。

HDOJ 3535-AreYouBusy

HDOJ 3535-AreYouBusy
AreYouBusy
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3450 Accepted Submission(s): 1342
Problem Description
Happy New Term!
As having become a junior, xiaoA recognizes that there is not much time for her to AC problems, because there are some other things for her to do, which makes her nearly mad.
What's more, her boss tells her that for some sets of duties, she must choose at least one job to do, but for some sets of things, she can only choose at most one to do, which is meaningless to the boss. And for others, she can do of her will. We just define the things that she can choose as "jobs". A job takes time , and gives xiaoA some points of happiness (which means that she is always willing to do the jobs).So can you choose the best sets of them to give her the maximum points of happiness and also to be a good junior(which means that she should follow the boss's advice)?
Input
There are several test cases, each test case begins with two integers n and T (0<=n,T<=100) , n sets of jobs for you to choose and T minutes for her to do them. Follows are n sets of description, each of which starts with two integers m and s (0<m<=100), there are m jobs in this set , and the set type is s, (0 stands for the sets that should choose at least 1 job to do, 1 for the sets that should choose at most 1 , and 2 for the one you can choose freely).then m pairs of integers ci,gi follows (0<=ci,gi<=100), means the ith job cost ci minutes to finish and gi points of happiness can be gained by finishing it. One job can be done only once.
Output
One line for each test case contains the maximum points of happiness we can choose from all jobs .if she can’t finish what her boss want, just output -1 .
Sample Input
3 3
2 1
2 5
3 8
2 0
1 0
2 1
3 2
4 3
2 1
1 1
3 4
2 1
2 5
3 8
2 0
1 1
2 8
3 2
4 4
2 1
1 1
1 1
1 0
2 1
5 3
2 0
1 0
2 1
2 0
2 2
1 1
2 0
3 2
2 1
2 1
1 5
2 8
3 2
3 8
4 9
5 10
Sample Output
5
13
-1
-1
Author
hphp
Source
2010 ACM-ICPC Multi-University Training Contest(10)——Host by HEU
Recommend
zhouzeyong | We have carefully selected several similar problems for you: 3033 1712 3449 2639 2159


本题分三种集合,第0种集合内至少要取1个任务;第1种集合内至多取1一个任务;第2种集合内没有任何限制。
集合内部是背包问题,这3种集合之间也是一个背包问题。
假设dp[i][j]表示前i个集合中,耗时为j时取得的最大幸福数量,则:
在第0种集合中,因为至少要取1个任务(耗时c,幸福数g),这个任务可以是本集合的第一个任务dp[i-1][j-c]+g,因为是第一个任务,所以基准是上一个集合i-1;也可以不是第一个任务dp[i][j-c]+g,基准就是本集合i;可以不取这个任务dp[i][j],所以dp[i][j]=max(dp[i][j], dp[i-1][j-c]+g, dp[i][j-c]+g),为了至少取一个任务,dp[i][j]必须小于其他2个,所以令dp[i][j]的初始值为-INF。
在第1种集合中,至多取1个任务,都是基于上一个集合,所以不取dp[i-1][j];取dp[i-1][j-c]+g。
在第2种集合中,是常规0/1背包问题,不取dp[i-1][j];第一次取dp[i-1][j-c]+g;不是第一次取dp[i][j-c]+g。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int kMaxN = 105, kINF = 0x7ffffff;
int dp[kMaxN][kMaxN];
int main()
{
	//freopen("input.txt", "r", stdin);
	int n, t;
	while (~scanf("%d %d", &n, &t))
	{
		for (int i = 0; i < kMaxN; i++)
			for (int j = 0; j < kMaxN; j++)
				dp[i][j] = -kINF;
		for (int i = 0; i < kMaxN; i++)
			dp[0][i] = 0;
		int m, s, c, g;
		for (int i = 1; i <= n; i++) { scanf("%d %d", &m, &s); if (s == 0) { while (m--) { scanf("%d %d", &c, &g); for (int j = t; j >=c; j--)
						dp[i][j] = max(dp[i][j], max(dp[i - 1][j - c] + g, dp[i][j - c] + g));
				}
			}
			else if (s == 1)
			{
				for (int j = t; j >= 0; j--)
					dp[i][j] = dp[i - 1][j];
				while (m--)
				{
					scanf("%d %d", &c, &g);
					for (int j = t; j >= c; j--)
						dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + g);
				}
			}
			else if (s == 2)
			{
				for (int j = t; j >= 0; j--)
					dp[i][j] = dp[i - 1][j];
				while (m--)
				{
					scanf("%d %d", &c, &g);
					for (int j = t; j >= c; j--)
						dp[i][j] = max(dp[i][j], max(dp[i - 1][j - c] + g, dp[i][j - c] + g));
				}
			}
		}
		printf("%d\n", max(dp[n][t], -1));
	}
	return 0;
}

本代码提交AC,用时31MS,内存1616K。

HDOJ 5418-Victor and World

HDOJ 5418-Victor and World
Victor and World
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 643 Accepted Submission(s): 268
Problem Description
After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are n countries on the earth, which are numbered from 1 to n. They are connected by m undirected flights, detailedly the i-th flight connects the ui-th and the vi-th country, and it will cost Victor's airplane wi L fuel if Victor flies through it. And it is possible for him to fly to every country from the first country.
Victor now is at the country whose number is 1, he wants to know the minimal amount of fuel for him to visit every country at least once and finally return to the first country.
Input
The first line of the input contains an integer T, denoting the number of test cases.
In every test case, there are two integers n and m in the first line, denoting the number of the countries and the number of the flights.
Then there are m lines, each line contains three integers ui, vi and wi, describing a flight.
1≤T≤20.
1≤n≤16.
1≤m≤100000.
1≤wi≤100.
1≤ui,vi≤n.
Output
Your program should print T lines : the i-th of these should contain a single integer, denoting the minimal amount of fuel for Victor to finish the travel.
Sample Input
1
3 2
1 2 2
1 3 3
Sample Output
10
Source
BestCoder Round #52 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5421 5420 5419 5416 5415


此题是可重复访问城市的旅行商问题(TSP),即从1号城市开始,经过每个城市至少一次,然后回到1号,问飞机消耗的最少燃料是多少。
根据题解,首先使用Floyd算法求出所有点对的最短路径dis[i][j],然后DP算法求解。
用一个整数s的二进制表示当前走过城市的状态,第i位为1表示第i个城市已经访问过,为0表示没访问过。dp[s][i]表示当前走过城市状态为s,且最后走过的城市编号为i,即到达了城市i。则有状态转移方程:
dp[s|(1<<i)][i]=min(dp[s][j]+dis[i][j])
条件为s&(1<<j)!=0且s&(1<<i)==0。
含义为:在s已经访问过j但是没有访问过i的情况下,转移到访问i的状态s|(1<<i)消耗的燃料为所有“s最后访问的是j消耗的燃料dp[s][j],加上从j走到i消耗的燃料之和”情况中的最小值。
最终结果就是s中所有位为1的状态,再从该状态回到城市1的燃料之和的最小值,即min(dp[(1<<n)-1][i]+dis[i][1])。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int kMaxN = 17, kINF = 0x3f3f3f3f;
int dis[kMaxN][kMaxN], dp[1 << kMaxN][kMaxN];
int n, m;
void Init()
{
	memset(dis, 0x3f, sizeof(dis));
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 1; i <= n; i++)
		dis[i][i] = 0;
}
void Floyd()
{
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
}
int main()
{
	freopen("input.txt", "r", stdin);
	int t, u, v, w;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d %d", &n, &m);
		Init();
		while (m--)
		{
			scanf("%d %d %d", &u, &v, &w);
			dis[u][v] = min(w, dis[u][v]);
			dis[v][u] = dis[u][v];
		}
		Floyd();
		dp[1][1] = 0;
		for (int status = 1; status < (1 << n); status++)//枚举状态
		{
			for (int i = 1; i <= n; i++)//枚举最后访问的城市
			{
				//if (status&(1 << (i-1))==0)//(1)
				if ((status&(1 << (i-1)))==0)//(2)i有没有访问过都可以
				{
					for (int j = 1; j <= n; j++)//枚举中间转折点
					{
						if (status&(1 << (j-1)))//(3)转折点j一定要访问过
							dp[status | (1 << (i-1))][i] = min(dp[status | (1 << (i-1))][i], dp[status][j] + dis[i][j]);
					}
				}
			}
		}
		int ans = kINF;
		for (int i = 1; i <= n; i++)
			ans = min(ans, dp[(1 << n) - 1][i] + dis[i][1]);
		printf("%d\n", n == 1 ? 0 : ans);
	}
	return 0;
}

本代码提交AC,用时717MS,内存10284K。
代码中需要注意一点,代码(2)一定不要写成了(1),要不然WA到死,&的优先级低于==,切记!
其实(2)处的if可以不要,因为本TSP问题可以重复访问某个城市,所以这里可以不判断下一步需要访问的城市之前有没有访问过,只是加了if能缩短时间;但是(3)处的if判断一定要,因为需要在城市j中转,j之前必须访问过。
另外查看大神的代码,发现很喜欢用0x3f3f3f3f而不是0x7fffffff作为程序中的无穷大,这是有道理的,详情看这篇博客

HDOJ 5417-Victor and Machine

HDOJ 5417-Victor and Machine
Victor and Machine
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 177 Accepted Submission(s): 91
Problem Description
Victor has a machine. When the machine starts up, it will pop out a ball immediately. After that, the machine will pop out a ball every w seconds. However, the machine has some flaws, every time after x seconds of process the machine has to turn off for y seconds for maintenance work. At the second the machine will be shut down, it may pop out a ball. And while it's off, the machine will pop out no ball before the machine restart.
Now, at the 0 second, the machine opens for the first time. Victor wants to know when the n-th ball will be popped out. Could you tell him?
Input
The input contains several test cases, at most 100 cases.
Each line has four integers x, y, w and n. Their meanings are shown above。
1≤x,y,w,n≤100.
Output
For each test case, you should output a line contains a number indicates the time when the n-th ball will be popped out.
Sample Input
2 3 3 3
98 76 54 32
10 9 8 100
Sample Output
10
2664
939
Source
BestCoder Round #52 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5421 5420 5419 5418 5416


有两种解法,一模拟,二推导公式。我采用的是第二种方法,根据x和w的大小关系,分为3种情况。
当w>x时,只可能启动的时候弹出小球,相邻两球弹出的时间间隔为x+y,因为0时刻会弹出一个球,所以总时间为(n-1)*(x+y)。
当w==x时,每隔(x+y)弹出2球,如果n为奇数,n-1为偶数,则需要花(n-1)/2*(x+y)时间,这里n-1减去了0时刻那个球,因为那个球不花时间;如果n为偶数,n-1为奇数,代入上式为(n-2)/2*(x+y),但是这里的n-1减去了一个球,最后还要隔x时间才弹出一个球,所以还需加上x,即(n-2)/2*(x+y)+x。
当w<x时,每x+y时间会弹出num=x/w+1个球,如果n不能整除num,则n/num是int型,即有n/num个完整的周期,还剩下n%num个球没弹出来,因为每个w时间弹一个球,所以只需间隔n%num-1次就可弹出n%num个球,总时间为(n/num)*(x+y)+(n%num-1)*w;如果n能整除num,则有n/num个完整的周期,我们先算前n/num-1个周期,时间为(n/num-1)*(x+y),最后一个周期,因为机器开启时刻会弹出一个球,所以只需间隔num-1次即可弹出这个周期剩余的球,加上w*(num-1)。
完整代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int x, y, w, n;
	while (scanf("%d %d %d %d", &x, &y, &w, &n) != EOF)
	{
		if (w > x)
			printf("%d\n", (n - 1)*(x + y));
		else if (w == x)
		{
			if (n & 1)
				printf("%d\n", ((n - 1) / 2)*(x + y));
			else
				printf("%d\n", ((n - 2) / 2)*(x + y) + x);
		}
		else
		{
			int num = x / w + 1;
			if (n % num == 0)
				printf("%d\n", (n / num - 1)*(x + y) + w * (num - 1));
			else
				printf("%d\n", (n / num)*(x + y) + (n % num - 1) * w);
		}
	}
	return 0;
}

本代码提交AC,用时0MS,内存1560K。

HDOJ 5392-Infoplane in Tina Town

HDOJ 5392-Infoplane in Tina Town
Infoplane in Tina Town
Time Limit: 14000/7000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1636 Accepted Submission(s): 385
Problem Description
There is a big stone with smooth surface in Tina Town. When people go towards it, the stone surface will be lighted and show its usage. This stone was a legacy and also the center of Tina Town’s calculation and control system. also, it can display events in Tina Town and contents that pedestrians are interested in, and it can be used as public computer. It makes people’s life more convenient (especially for who forget to take a device).
Tina and Town were playing a game on this stone. First, a permutation of numbers from 1 to n were displayed on the stone. Town exchanged some numbers randomly and Town recorded this process by macros. Town asked Tine,”Do you know how many times it need to turn these numbers into the original permutation by executing this macro? Tina didn’t know the answer so she asked you to find out the answer for her.
Since the answer may be very large, you only need to output the answer modulo 3∗230+1=3221225473 (a prime).
Input
The first line is an integer T representing the number of test cases. T≤5
For each test case, the first line is an integer n representing the length of permutation. n≤3∗106
The second line contains n integers representing a permutation A1...An. It is guaranteed that numbers are different each other and all Ai satisfies ( 1≤Ai≤n ).
Output
For each test case, print a number ans representing the answer.
Sample Input
2
3
1 3 2
6
2 3 4 5 6 1
Sample Output
2
6
Source
BestCoder Round #51 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5395 5394 5393 5390 5389


此题和POJ 2369-Permutations类似,只是测试样例更多,数据规模更大,最后还要对某个大数取模。所以在求所有循环节长度的最小公倍数的时候,不能使用gcd转换的方法,需要先后使用因式分解和快速幂算法。
参考下面的例子理解分解质因数法求最小公倍数的方法。
60=2×2×3×5
18=2×3×3
lcm(60,18)=180=2×2×3×3×5
通过观察可以看出规律,要求a,b的最小公倍数,先将a和b分解成质因数相乘的形式,对于每一个质因子x,取x在a和b中出现频率最高的数作为x在最小公倍数中的频率。比如2在60中出现2次,但在18中只出现1次,所以2在最小公倍数180中也出现2次,同理质因子3和5分别出现2次和1次。
假设某个质因子x出现y次,则最后要计算x^ymodp,可以使用快速幂方法提高速度,该方法很好理解,将y看成二进制形式,如果y为偶数,则x^y=(x*x)^{y/2};如果y为奇数,则x^y=x*x^{y-1},y-1就是偶数了。同时modp就是快速幂取模了。
完整代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int kMaxN = 3000005, kNumPrime = 269;
const ULL kMod = 3221225473;
bool visited[kMaxN];
int permutation[kMaxN];
int prime[kNumPrime] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723 };
int prime_times[kMaxN];
//求x的所有质因子及其频率
void GetPrimeFactor(int x)
{
	for (int i = 0; i < kNumPrime; i++)
	{
		int tmp = 0;
		while (x%prime[i] == 0)
		{
			tmp++;
			x /= prime[i];
		}
		if (tmp > prime_times[prime[i]])
			prime_times[prime[i]] = tmp;
		if (x == 1)
			return;
	}
	prime_times[x]++;
}
//快速幂取模x^ymod(kMod)
ULL QuickPow(ULL x, ULL y)
{
	ULL ans = 1;
	while (y)
	{
		if (y & 1)
			ans = (ans*x)%kMod;
		x = (x*x) % kMod;
		y >>= 1;
	}
	return ans;
}
int main()
{
	int t, n, len;
	ULL ans;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		memset(visited, false, kMaxN);
		memset(prime_times, 0, kMaxN);
		for (int i = 1; i <= n; i++)
			scanf("%d", &permutation[i]);
		for (int i = 1; i <= n; i++)
		{
			if (!visited[i])
			{
				visited[i] = true;
				int j = permutation[i];
				len = 1;
				while (j != i)
				{
					visited[j] = true;
					j = permutation[j];
					len++;
				}
				GetPrimeFactor(len);
			}
		}
		ans = 1;
		for (int i = 2; i < n; i++)
			if (prime_times[i] != 0)
				ans = (ans*QuickPow(i, prime_times[i])) % kMod;
		printf("%I64un", ans);
	}
	return 0;
}

本代码提交AC,用时5101MS,内存27984K。

HDOJ 5391-Zball in Tina Town

HDOJ 5391-Zball in Tina Town
Zball in Tina Town
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 817 Accepted Submission(s): 471
Problem Description
Tina Town is a friendly place. People there care about each other.
Tina has a ball called zball. Zball is magic. It grows larger every day. On the first day, it becomes 1 time as large as its original size. On the second day,it will become 2 times as large as the size on the first day. On the n-th day,it will become n times as large as the size on the (n-1)-th day. Tina want to know its size on the (n-1)-th day modulo n.
Input
The first line of input contains an integer T, representing the number of cases.
The following T lines, each line contains an integer n, according to the description.
T≤10^5,2≤n≤10^9
Output
For each test case, output an integer representing the answer.
Sample Input
2
3
10
Sample Output
2
Source
BestCoder Round #51 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5395 5394 5393 5392 5390
 


本题关键在于理解题意,在BestCoder中文描述中是第n天变大n倍,这样不就是n+1倍了吗,当时一直按这个思路,以为是A176787这个序列,后来看英文以及别人的解释才明白。

On the n-th day,it will become n times as large as the size on the (n-1)-th day.

所以第n天的大小就是第n-1天的n倍,也就是n!。
最终结果即为(n-1)!modn,如果n为合数,n一定能分解成n以内的某些个数相乘,所以结果为0;如果n为素数,根据威尔逊定理,有

所以结果为-1modn=n-1
当n=2和4时,需要特殊处理。完整代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
bool IsPrime(int x)
{
	for (int i = 2; i*i <= x; i++)
		if (x%i == 0)
			return false;
	return true;
}
int main()
{
	int t, n;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		if (n == 2)
			printf("1n");
		else if (n == 4)
			printf("2n");
		else if (IsPrime(n))
			printf("%dn", n - 1);
		else
			printf("0n");
	}
	return 0;
}

本代码提交AC,用时967MS,内存1576K。