Cerinta completa

You are given an array A = [1, 2, 3, …, n]:

  1. How many sequences (S1) can you get after exact k adjacent swaps on A?

  2. How many sequences (S2) can you get after at most k swaps on A?

An adjacent swap can be made between two elements of the Array A, A[i] and A[i+1] or A[i] and A[i-1].
A swap otherwise can be between any two elements of the array A[i] and A[j] ∀ 1 ≤ i, j ≤ N, i ≠ j.

Input Format

First and only line contains n and k separated by space.

Constraints

1 ≤ n ≤ 2500
1 ≤ k ≤ 2500

Output Format

Output S1 % MOD and S2 % MOD in one line, where MOD = 1000000007.

Sample Input

3 2

Sample Output

3 6

Explanation

Original array: [1, 2, 3]
1. After 2 adjacent swaps:
We can get [1, 2, 3], [2, 3, 1], [3, 1, 2] ==> S1 == 3

2. After at most 2 swaps:
1) After 0 swap: [1, 2, 3]
2) After 1 swap: [2, 1, 3], [3, 2, 1], [1, 3, 2].
3) After 2 swaps: [1, 2, 3], [2, 3, 1], [3, 1, 2]
==> S2 == 6

Limbajul de programare folosit: cpp14

Cod:

//swappermutation.cpp
//Swap Permutation
//Weekly Challenges - Week 5
//Author: derekhh

#include<iostream>
#include<algorithm>
using namespace std;

const int MOD = 1000000007;
long long f[2501][2501], fs[2501][2501];
long long g[2501][2501];

int main()
{
	int n, k;
	cin >> n >> k;
	f[1][0] = fs[1][0] = 1;
	for (int i = 1; i <= k; i++)
		fs[1][i] = 1;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			if (j != min(i - 1, j))
				f[i][j] = (fs[i - 1][j] + MOD - fs[i - 1][j - min(i - 1, j) - 1]) % MOD;
			else
				f[i][j] = fs[i - 1][j];

			//printf("f[%d][%d] = %d\n", i, j, f[i][j]);

			if (j == 0)
				fs[i][j] = f[i][j] % MOD;
			else
				fs[i][j] = (fs[i][j - 1] + f[i][j]) % MOD;
		}
	}
	
	g[0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			if (i == j)
				g[i][j] = 1;
			else
				g[i][j] = (g[i - 1][j - 1] + (i - 1) * g[i - 1][j]) % MOD;

	int ret1 = 0, ret2 = 0;
	for (int i = 0; i <= k; i++)
		if (i % 2 == k % 2)
			ret1 = (ret1 + f[n][i]) % MOD;

	for (int i = 0; i <= n; i++)
		if (n - i <= k)
			ret2 = (ret2 + g[n][i]) % MOD;

	cout << ret1 << " " << ret2 << endl;
	return 0;
}

Scor obtinut: 1.0

Submission ID: 464604983

Link challenge: https://www.hackerrank.com/challenges/swappermutation/problem

Swap Permutation