Pizza Stack

Kamaldeep is good at making pizzas. Generally he gets requests to serve N pizzas at once. He serves them in the form of a stack. A pizza should be treated as a circular disk with some radius.

Kamaldeep needs to take care that when he places a pizza on the top of the stack the radius of the pizza should not exceed the radius of the largest pizza in the stack by more than 1. Additionally all radii should be positive integers, and the bottom most pizza should have its radius as 1. Kamaldeep is week in maths :P, so he wants you to find out in how many ways can he create a stack containing N pizzas.

Input

First line of the input contains T (T <= 1000) denoting the number of test cases.

T lines follow each containing a single integer N (1 <= N <= 1000) denoting the size of the required stack.

Output

For each case the output should be a single integer representing the number of ways a stack of size N can be created. As

the answer can be large print it modulo 1000000007.

ANS------->

dp[i][j] -> stack size of i with j different value .

dp[i][j] = j*dp[i-1][j] + dp[i-1][j-1];

1. #include <iostream>
2. using namespace std;
3.  
4. int main()
5. {
6. int t ;
7. cin >> t;
9. long long mo = 1000000007;
10.  
11. long long dp[1002][1002];
12. long long top[1002];
14. for(int i=0 ; i < 1002 ; i++)
15. for(int j=0 ; j < 1002 ; j++)
16. dp[i][j]=0;
17.  
18. dp[1][1]=1 ;
19. top[1]=1;
22. for(int i=2 ; i < 1002 ; i++){
23. long long temp = 0 ;
24. for(int j=1; j<=i; j++){
25. dp[i][j]=j*dp[i-1][j]%mo + dp[i-1][j-1]%mo;
26. temp=(temp+dp[i][j])%mo;
27. }
28. top[i]=temp;
29. }
33. while(t--){
35. int val ;
36. cin >> val ;
37. cout << top[val] << endl ;
39. }
41.  
42. return 0;
43. }

Randomness

You’re given a string S of N characters. It’s known that the string consists of lowercase latin letters. The string is generated randomly. That means that every symbol is chosen randomly and independently from others from the set {‘a’, ‘b’, …, ‘z’}. All the letters has equal probability to appear.

You’re given Q queries on this string. Each query is of the form P C, where P is an integer between 1 and N (both inclusive) and C is a character from the set {‘a’, ‘b’, …, ‘z’}. Both P and C were chosen at random and independently from other queries.

When you have a query of the form P C you have to change the Pth symbol of S to C. After every change we ask you to output the number of distinct nonempty sub-strings of S.

Input Format
The first line of input consists of two single space separated integers N and Q - the length of the string S and the number of queries respectively.

The second line contains the string S itself.

The following Q lines describe the queries in the form P C, where P and C are also separated with a single space.

Constraints

4 ≤ N ≤ 75000
4 ≤ Q ≤ 75000

Output Format
Output Q lines. Output the number of distinct substrings of S after the ith query on theith line of the output.

Sample Input

4 4 
aaab
1 a
2 b
3 c
4 d

Sample Output

7
7
9
10

Explanation

after replacing the character at 1st index with a, we still have the original string aaab. The total non empty substrings of aaab are

a b aa ab aaa aab aaab

hence 7.

after replacing the character at 2nd index with b, we have the string abab. The total non empty substrings of abab are

a b ab ba aba bab abab

hence 7.

after replacing the character at 3rd index with c, we have the string abcb. The total non empty substrings of abcb are

a b c ab bc cb abc bcb abcb

hence 9.

after replacing the character at 4th index with d, we have the string abcd. The total non empty substrings of abcd are

a b c d ab bc cd abc bcd abcd

hence 10.

Scoring

There are 12 test cases.

The first four test cases N = 100 and Q = 500
The next four test cases N = 75000 and Q = 10
The last four test cases N = 75000 and Q = 75000

solution-->

The solution consists of constructing the suffix array and then finding the number of distinct substrings based on the Longest Common Prefixes.

One key observation here is that:

If you look through the prefixes of each suffix of a string, you have covered all substrings of that string.

Let us take an example: BANANA

Suffixes are:

0) BANANA
1) ANANA
2) NANA
3) ANA
4) NA
5) A

It would be a lot easier to go through the prefixes if we sort the above set of suffixes, as we can skip the repeated prefixes easily.

Sorted set of suffixes:

5) A
3) ANA
1) ANANA
0) BANANA
4) NA
2) NANA

From now on, 

LCP = Longest Common Prefix of 2 strings.

Initialize

ans = length(first suffix) = length("A") = 1.

Now consider the consecutive pairs of suffixes, i.e, [A, ANA], [ANA, ANANA], [ANANA, BANANA], etc. from the above set of sorted suffixes.

We can see that,

LCP("A", "ANA") = "A".

All characters that are not part of the common prefix contribute to a distinct substring. In the above case, they are 'N' and 'A'. So they should be added to ans.

So we have, 

1 2	ans += length("ANA") - LCP("A", "ANA") ans = ans + 3 - 1 = ans + 2 = 3

Do the same for the next pair of consecutive suffixes: ["ANA", "ANANA"]

1 2 3 4

LCP("ANA", "ANANA") = "ANA". ans += length("ANANA") - length(LCP) => ans = ans + 5 - 3 => ans = 3 + 2 = 5.

Similarly, we have:

1 2	LCP("ANANA", "BANANA") = 0 ans = ans + length("BANANA") - 0 = 11

1 2	LCP("BANANA", "NA") = 0 ans = ans + length("NA") - 0 = 13

1 2	LCP("NA", "NANA") = 2 ans = ans + length("NANA") - 2 = 15

Hence the number of distinct substrings for the string "BANANA" = 15.

code---->

#include<iostream>

#include<string>

#include<algorithm>

using namespace std ;

int LCP(string s , string s1){

int x=s.size();

int y=s1.size();

if(x>y)

    x=y;

    int count=0 ;

    for(int i=0 ; i < x ;i++){

        if(s.at(i)==s1.at(i))

            count++;

        else

         break ;

    }

return count ;

}

void check(string s){

    int x= s.size();

    string ss[x];

    

    for(int i=0 ; i<x ;i++)

        ss[i]= s.substr(i);     

         sort(ss,ss+x);

         int ans=0;

         ans=ss[0].size();

      for(int i=1 ; i<x ; i++)

    ans+=( ss[i].size() - LCP(ss[i],ss[i-1]));

    cout << ans << endl ;    

}

int main(){

    int x=0,y=0 ;   

    cin >> x >> y ;

     string s ;

    cin >> s ;

    while(y--){

          int p ;

          char z ;

         cin >>p >> z ;

         s[p-1]=z;

         check(s);

     }

    return 0 ;   

}

Volleyball Match

Tatyana is a big sports fan and she likes volleyball a lot! She writes down the final scores of the game after it has ended in her notebook.

If you are not familiar with the rules of volleyball, here’s a brief:

• 2 teams play in total
• During the course of the game, each team gets points, and thus increases its score by 1.
• The initial score is 0 for both teams.

The game ends when

• One of the teams gets 25 points and another team has < 24 points ( strictly less than 24).
• If the score ties at 24:24, the teams continue to play until the absolute difference between the scores is 2.

Given the final score of a game in the format A:B i.e., the first team has scored Apoints and the second has scored B points, can you print the number of different sequences of getting points by teams that leads to this final score?

Input Format
The first line contains A and the second line contains B.

Constraints

0 ≤ A , B ≤ 109

Output Format
Output the number of different sequences of getting points by the teams that leads to the final score A : B. Final means that the game should be over after this score is reached. If the number is larger than 109+7, output number modulo 109 + 7. Print 0 if no such volleyball game ends with the given score.

Example input #00

3
25

Example output #00

2925

Example input #01

24
17

Example output #01

0

Explanation #01

There’s no game of volleyball that ends with a score of 24 : 17.

solution -->

Lets consider there are r−1 blocks, so that, there will be r spaces to be filled (including the left of the left most block and right of the right most block). Now, n identical things should be filled in these spaces. There are n+r−1 things in that line now, which can be arranged in (n+r−1)!ways.

But, we should avoid the arrangements between the n things and r−1 blocks, since they are identical.

So, the final answer is

(n+r−1)!n!(r−1)!=C(n+r−1,r−1).

code-->

#include<iostream>
using namespace std ;

long long fact[100];
int  p = 1000000007 ;

long long pow(long long a , int b){
    long long x=1 , y=a; 
     while(b){
         if(b%2==1){
         x=x*y;
         x=x%p;
     }
     y=y*y;
    y=y%p ;
    b=b/2;
     }
    return x ;
    
}
int max(int a , int b ){
    return a>b?a:b ;
}

int main(){
    
int a,b ;
    
    cin >> a >> b ;
    
    fact[0]=1 ;
    
    for(int i=1 ; i<100 ;i++)
        fact[i]=(fact[i-1]*(long long)i)%p;
    
    
    if( (a<25 && b<25) || abs(a-b)<2){
        cout <<"0";
        return  0 ;
    }
    
    if(a>=24 && b>=24){
        
        if(abs(a-b)!=2){
             cout <<"0";
        return  0 ;
        }
        
        int z =max(a,b)-2;
        z=z-24;
        long long q= (fact[24]*fact[24])%p ;
        long long ans =(fact[24+25-1]*pow(q,p-2))%p;
        
   long long zz=pow(2,z);        

            ans=(ans*zz)%p;
        
        cout << ans << endl ;
        return 0 ;
          }
    
    
        int y;
        if(a>b)
            y=b;
        else
           y=a; 
  
            long long z = (fact[y]*fact[25-1])%p  ;
        long long ans=(fact[25+y-1]*pow(z,p-2))%p;       
         
    cout << ans << endl ;
    
    return 0 ;
}