Problem 1: Auction Ceremony

Points:

Small Case: 10 Answer: 266

Large Case: 25 Answer: 49306943

In the Indian Premier League Auction, there are N players and N team-owners. The owners get the chance to select in order {1,2,...,N}.
At each owners turn, he can either buy a non-selected player, or re-buy a player selected by someone else with value greater than its previous cost.
If an owner buys a player already bought by some other owner, the losing owner immediately gets the chance to select next.
According to rules, each player can be re-bought maximum of T times(bought maximum of T+1 times) and every owner must get at least one player.

For e.g. for T=1 and N=3, with owners (x,y,z) and players (1,2,3), selections can be made in seven ways as:

x1, y2, z3
x1, y2, z1, x3
x1, y2, z1, x2, y3
x1, y2, z2, y3
x1, y2, z2, y1, x3
x1, y1, x2, z3
x1, y1, x2, z3
x1, y1, x2, z2, x3

You can assume players are same and their order does not matter, For example: x1,y2,z3 and x2,y1,z3 are same cases

You need to output the number of ways modulo 100000007

Given the values of N and T, what is the number of ways in which this can be done?

Small Case: N= 5, T=1
Large Case: N= 51, T=8

Solution:

We know that t-restricted stirling number S2t(n,k) of second kind is defined as the number of partitions of {1, . . . , n} into k blocks of size at most t.

For t>=0 and n>=0, number of scenatios with (n+1) buyers and (n+1) players is given by:

Reference: David Applegate and N. J. A. Sloane, The Gift Exchange Problem, AT&T Shannon Labs, 1990,Theorem 1

Code:

#include <stdio.h>
#include <string.h>
#define mod 100000007

long long E[100][1000], t;

long long nCr(long long n, long long r)
{
  if(n<r)
    return 0;
  if(n-r<r)
    r=n-r;
  long long res=1,min=n-r;
  while(n>min && r>1)
  {
    res *= n;
    n--;
    if(res%r==0)
      while(res%r==0 && r>1)
      { 
        res/=r;
        r--;
      }
  }
  if(n>min)
    while(n>min)
    {  res *= n;n--;}
  if(r>1)
  {
    res/=r;
    r--;
  }
  return res;
}

long long E_Cal(long long n, long long k)
{
  int i;
  if(E[n][k]==-1)
  {
    E[n][k]=0;
    if(k>=n && k<=(t+1)*n)
    {
      for(i=0;i<=t;i++)
      {
        E[n][k] = (E[n][k] + ((nCr(k-1,i)%mod) * (E_Cal(n-1,k-1-i)%mod))%mod)%mod;
      }
    }
  }
  return E[n][k];
}

int main()
{
  int n,k;
  long long sum=0;
  scanf("%d%lld",&n,&t);
  n--;
  memset(E,-1,sizeof(E));
  E[0][0]=1;
  for(k=n;k<=(t+1)*n;k++)
    sum = (sum + E_Cal(n,k))%mod;
  printf("%lld\n",sum);
}