11 months ago

PoGo 2.5k

Hyderabad

Number Game  :

Number game
You are given the first M natural numbers. You have to arrange these numbers in an array A such that there is no index / for which A[i] + 1 = A[i + 1].
Find the count of such arrays that can be constructed by using the first N natural numbers

Function description

Complete the solve function. This function takes the following parameter and returns the count of all possible arrangements:
•N: Represents the value of N

Input format for custom testing

Note: Use this input format if you are testing against custom input or writing code in a
language where we don't provide boilerplate code.
• The first line contains T, which represents the number of test cases.
• For each test case:

• First line contains a single integer N

Output format

For each test case,  print the number in a new line of arrays that can be constructed modulo 10⁹ + 7

Constraints

1 ≤ T ≤ 10⁵1  ≤ N ≤ 10⁵

Sample Input              Sample Output

2                              3
3                              1
2

Equations and queries :

Equations and queries

Given an array A of size N. There are M equations of the form I r. which denote the value of / r (denotes the value A_l + A_l+1+. --+-A_r). You have Q queries in the form x y, where you need to find the value of A[x] = y. For each query, check whether the value
can be found using the M equations. If the value can be found, return 1 Otherwise, return O

Function description

Complete the function solve. This function takes the following 5 parameters. 

• N. Represents the size of the array
• M: Represents the number of equations
• Q. Represents the number of queries
• Equations: Represents the elements describing the equations
• Queries: Represents the elements defining the queries

Input format

Note Use this input format if you are testing against custom input or writing code
in a language where we don't provide boilerplate code.
The first line contains a single integer

• N denoting the size of the array
• The second line contains a single integer M denoting the number equations
• The third line contains a single integer Q denoting the number of queries.
• The next M line contains two integers / and
• r, describing an equation.
• The next Q line contains two integers Xp and y, describing a query.

Output format

Print O space-separated integers denoting the answer to the queries.

Constraints

• 1 ≤ N≤ 2 * 10⁵
• 1 ≤ M ≤ min(2 + 105, MUN+1))
• 1≤0≤2+10⁵
• 1≤4≤S NVi€[1,M]
• 1 St, ≤ y ≤ N Vi € [1, Q]

Saple Input
4
3
2
1  1
1  3
2  4
2  3
4  4

Sample Output

1 1

18 months ago

yash • 0

Varanasi

#include <iostream>

#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

const int MAX_N = 100000;

vector<long long> solve()

{

    vector<long long> dp(MAX_N + 1, 0);

    dp[1] = 1;

    dp[2] = 1;

    dp[1] = dp[2] = 1;

    for (int n = 3; n <= MAX_N; n++)

    {

        dp[n] = ((n - 1) * dp[n - 1] % MOD + (n - 2) * dp[n - 2] % MOD) % MOD;

    }

    return dp;

}

int main()

{

    vector<long long> res = solve();

    int t;

    cin >> t;

    while (t--)

    {

        int n;

        cin >> n;

        cout << res[n] << endl;

    }

    return 0;

}