HackerRank Combinatorics – Permutation Problem

Challenge: Permutation Problem

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734952

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/permutation-problem/problem

Cerinta

How many n-digit numbers (without leading zeros) are there such that no digit occurs more than k times?  

As the count of such n-digit numbers can be very large, print the answer mod (10<sup>9</sup>+7)  

**Input Format**  

The first line contains an integer, _T_ , the number of test cases. This is followed by _T_ lines each containing 2 space separated integers, _n_ and _k_  


**Constraints**  

_T_ ≤ 100000  
1 ≤ _n_ ≤ 1000  
1 ≤ _k_ ≤ 10<sup>9</sup>

**Sample Input**

    2
    2 3
    2 1

**Sample Output**

    90
    81

**Explanation**  
Case 1: A number can appear three times. So we have 9 (all except 0) numbers for first digit and 10 numbers for the second digit.  
Case 2: A number can appear only once. So we have 9 choices for the first digit and 9(all except the first one) for the second digit.

Cod sursa

//permutation-problem.cpp
//Permutation Problem
//Ad Infinitum - Math Programming Contest June'14
//Author: derekhh

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

const int MOD = 1000000007;

int f[1001][1001][11], g[1001][1001], c[1001][1001];

void init()
{
	for (int i = 1; i <= 1000; i++)
		c[i][0] = 1, c[i][1] = i, c[i][i] = 1;

	for (int i = 2; i <= 1000; i++)
		for (int j = 2; j <= 1000; j++)
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}

int foo(int i,int j,int k)
{
	if (f[i][j][k] != -1) return f[i][j][k];
	if (i == 0) return f[i][j][k] = 1;

	int val1 = (k * (long long)foo(i - 1, min(i - 1, j), k)) % MOD;
	int val2 = (k * (long long)c[i - 1][j]) % MOD;
	int val3 = ((long long)val2 * foo(i - j - 1, min(i - j - 1, j), k-1)) % MOD;
	
	return f[i][j][k] = (val1 + MOD - val3) % MOD;
	
	/*
	int ret = 0;
	for (int l = 1; l <= min(i, j); l++)
		ret = (ret + (long long)c[i][l] * foo(i - l, min(i - l, j), k - 1)) % MOD;
	return f[i][j][k] = ret;
	*/
}

int main()
{
	memset(f, -1, sizeof(f));
	init();

	for (int i = 1; i <= 1000; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			for (int k = 1; k <= 10; k++)
			{
				f[i][j][k] = foo(i, j, k);
			}
		}
	}

	for (int i = 1; i <= 1000; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			int val1 = (9 * (long long)foo(i - 1, min(i - 1, j), 10)) % MOD;
			int val2 = (9 * (long long)c[i - 1][j]) % MOD;
			int val3 = ((long long)val2 * foo(i - j - 1, min(i - j - 1, j), 9)) % MOD;
			g[i][j] = (val1 + MOD - val3) % MOD;
		}
	}
	int t;
	cin >> t;
	while (t--)
	{
		int n, k;
		cin >> n >> k;
		cout << g[n][min(n, k)] << endl;
	}
	return 0;
}