Se dice que un conjunto ordenado de enteros es un conjunto especial si para cada elemento del conjunto X , el conjunto no contiene el elemento X + 1 . Dado un número entero N , la tarea es encontrar el número de conjuntos especiales cuyo elemento más grande no sea mayor que N. Dado que el número de conjuntos especiales puede ser muy grande, imprima la respuesta módulo 10 9 + 7 .
Ejemplo:
Entrada: N = 3
Salida: 5
{1}, {2}, {3}, {1, 3} y {3, 1} son los
únicos conjuntos especiales posibles.
Entrada: N = 4
Salida: 10
Enfoque: Este problema se puede resolver mediante programación dinámica . Cree una array dp[][] donde dp[i][j] almacena la cantidad de conjuntos especiales de longitud i que terminan en j . Ahora, la relación de recurrencia será:
dp[i][j] = dp[i – 1][1] + dp[i – 1][2] + … + dp[i – 1][j – 2]
dp[i][j] puede ser calculado en O(1) tomando la suma del prefijo del dp anterior [i – 1] una vez.
Ahora los conjuntos especiales totales de tamaño i se pueden calcular multiplicando dp[i][n] con factorial(i) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2 * 1000 + 10;
const int MOD = 1e9 + 7;
// To store the states of the dp
ll dp[MAX][MAX];
// Function to return (a + b) % MOD
ll sum(ll a, ll b)
{
return ((a % MOD) + (b % MOD)) % MOD;
}
// Function to return (a * b) % MOD
ll mul(ll a, ll b)
{
return ((a % MOD) * (b % MOD)) % MOD;
}
// Function to return the count
// of special sets
int cntSpecialSet(int n)
{
// Fill the dp[][] array with the answer
// for the special sets of size 1
for (int i = 1; i <= n; i++) {
dp[1][i] = 1;
// Take prefix sum of the current row which
// will be used to fill the next row
dp[1][i] += dp[1][i - 1];
}
// Fill the rest of the dp[][] array
for (int i = 2; i <= n; i++) {
// Recurrence relation
for (int j = 2; j <= n; j++) {
dp[i][j] = dp[i - 1][j - 2];
}
// Calculate the prefix sum
for (int j = 1; j <= n; j++) {
dp[i][j] = sum(dp[i][j], dp[i][j - 1]);
}
}
ll ways(1), ans(0);
for (int i = 1; i <= n; i++) {
// To find special set of size i
ways = mul(ways, i);
// Addition of special sets of all sizes
ans = sum(ans, mul(ways, dp[i][n]));
}
return ans;
}
// Driver code
int main()
{
int n = 3;
cout << cntSpecialSet(n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 2 * 1000 + 10;
static int MOD = (int) (1e9 + 7);
// To store the states of the dp
static long [][]dp = new long[MAX][MAX];
// Function to return (a + b) % MOD
static long sum(long a, long b)
{
return ((a % MOD) + (b % MOD)) % MOD;
}
// Function to return (a * b) % MOD
static long mul(long a, long b)
{
return ((a % MOD) * (b % MOD)) % MOD;
}
// Function to return the count
// of special sets
static long cntSpecialSet(int n)
{
// Fill the dp[][] array with the answer
// for the special sets of size 1
for (int i = 1; i <= n; i++)
{
dp[1][i] = 1;
// Take prefix sum of the current row which
// will be used to fill the next row
dp[1][i] += dp[1][i - 1];
}
// Fill the rest of the dp[][] array
for (int i = 2; i <= n; i++)
{
// Recurrence relation
for (int j = 2; j <= n; j++)
{
dp[i][j] = dp[i - 1][j - 2];
}
// Calculate the prefix sum
for (int j = 1; j <= n; j++)
{
dp[i][j] = sum(dp[i][j], dp[i][j - 1]);
}
}
long ways = 1, ans = 0;
for (int i = 1; i <= n; i++)
{
// To find special set of size i
ways = mul(ways, i);
// Addition of special sets of all sizes
ans = sum(ans, mul(ways, dp[i][n]));
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int n = 3;
System.out.println(cntSpecialSet(n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach
# Function to print the nodes having
# maximum and minimum degree
def minMax(edges, leng, n) :
# Map to store the degrees of every node
m = {};
for i in range(leng) :
m[edges[i][0]] = 0;
m[edges[i][1]] = 0;
for i in range(leng) :
# Storing the degree for each node
m[edges[i][0]] += 1;
m[edges[i][1]] += 1;
# maxi and mini variables to store
# the maximum and minimum degree
maxi = 0;
mini = n;
for i in range(1, n + 1) :
maxi = max(maxi, m[i]);
mini = min(mini, m[i]);
# Printing all the nodes
# with maximum degree
print("Nodes with maximum degree : ",
end = "")
for i in range(1, n + 1) :
if (m[i] == maxi) :
print(i, end = " ");
print()
# Printing all the nodes
# with minimum degree
print("Nodes with minimum degree : ",
end = "")
for i in range(1, n + 1) :
if (m[i] == mini) :
print(i, end = " ");
# Driver code
if __name__ == "__main__" :
# Count of nodes and edges
n = 4; m = 6;
# The edge list
edges = [[ 1, 2 ], [ 1, 3 ],
[ 1, 4 ], [ 2, 3 ],
[ 2, 4 ], [ 3, 4 ]];
minMax(edges, m, 4);
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
static int MAX = 2 * 1000 + 10;
static int MOD = (int) (1e9 + 7);
// To store the states of the dp
static long [,]dp = new long[MAX, MAX];
// Function to return (a + b) % MOD
static long sum(long a, long b)
{
return ((a % MOD) + (b % MOD)) % MOD;
}
// Function to return (a * b) % MOD
static long mul(long a, long b)
{
return ((a % MOD) * (b % MOD)) % MOD;
}
// Function to return the count
// of special sets
static long cntSpecialSet(int n)
{
// Fill the dp[,] array with the answer
// for the special sets of size 1
for (int i = 1; i <= n; i++)
{
dp[1, i] = 1;
// Take prefix sum of the current row which
// will be used to fill the next row
dp[1, i] += dp[1, i - 1];
}
// Fill the rest of the dp[,] array
for (int i = 2; i <= n; i++)
{
// Recurrence relation
for (int j = 2; j <= n; j++)
{
dp[i, j] = dp[i - 1, j - 2];
}
// Calculate the prefix sum
for (int j = 1; j <= n; j++)
{
dp[i, j] = sum(dp[i, j], dp[i, j - 1]);
}
}
long ways = 1, ans = 0;
for (int i = 1; i <= n; i++)
{
// To find special set of size i
ways = mul(ways, i);
// Addition of special sets of all sizes
ans = sum(ans, mul(ways, dp[i, n]));
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int n = 3;
Console.WriteLine(cntSpecialSet(n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
b// JavaScript implementation of the approach
const MAX = 2 * 1000 + 10;
const MOD = 1e9 + 7;
// To store the states of the dp
let dp = new Array(MAX).fill(0).map(()=>new Array(MAX).fill(0));
// Function to return (a + b) % MOD
function sum(a, b)
{
return ((a % MOD) + (b % MOD)) % MOD;
}
// Function to return (a * b) % MOD
function mul(a, b)
{
return ((a % MOD) * (b % MOD)) % MOD;
}
// Function to return the count
// of special sets
function cntSpecialSet(n)
{
// Fill the dp[][] array with the answer
// for the special sets of size 1
for (let i = 1; i <= n; i++) {
dp[1][i] = 1;
// Take prefix sum of the current row which
// will be used to fill the next row
dp[1][i] += dp[1][i - 1];
}
// Fill the rest of the dp[][] array
for (let i = 2; i <= n; i++) {
// Recurrence relation
for (let j = 2; j <= n; j++) {
dp[i][j] = dp[i - 1][j - 2];
}
// Calculate the prefix sum
for (let j = 1; j <= n; j++) {
dp[i][j] = sum(dp[i][j], dp[i][j - 1]);
}
}
let ways = 1 , ans = 0;
for (let i = 1; i <= n; i++) {
// To find special set of size i
ways = mul(ways, i);
// Addition of special sets of all sizes
ans = sum(ans, mul(ways, dp[i][n]));
}
return ans;
}
// Driver code
let n = 3;
document.write(cntSpecialSet(n),"</br>");
/// This code is contributed by shinjanpatra
</script>
Producción:
5
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(MAX 2 )