Light OJ: 1144 – Ray Gun

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1144

Solution Idea:
There are many observations to make in order to get to a working solution.

  • For every lattice point (i, j), the ray that intersects it is unique and it’s identified by the pair , where g is the gcd of i and j.
  • The problem is now reduced to counting the number of irreducible fractions such that a ≤ N and b ≤ M. This is the same as counting for every i between 1 and N, the amount of numbers in the range [1, M] that are coprime with i.
  • Consider a certain number x with prime factors p1, p2. How do we know how many numbers in range [1, M] are coprime with it? That’s equal to M minus the amount of multiples of p1 minus the amount of multiples of p2 plus the amount of multiples of p1 * p2. This is inclusion-exclusion, and in general, if the amount of elements is even, we add, otherwise, we subtract.
  • So now we have a working (but slow) solution: Iterate over every i in the range [1, N] and for every i, factorize it, try out all combinations of primes and then, for every combination that results in a number k, add if the amount of primes is even or subtract if the amount of primes is odd.
  • The previous approach is very slow for two reasons: You’ll be factorizing each number every time and you’ll be doing a lot of repeated work. Every combination of primes you try out at each step will result in a certain number k. A crucial observation is that the higher exponent of that number k will be 1, because we’re trying combinations of different primes. Another crucial observation is that this number k will be seen times in total. Finally, each time we see it, it will contribute by to the final answer (or if the amount of primes is odd).
  • Knowing all this, we can precalculate a lot of stuff and then solve each test case in O(N). We should precalculate the amount of prime factors of every number in the range [1, 106] (this can be done with a simple sieve), and we should cross out numbers that have some prime with an exponent higher than 1 (in other words, multiples of some square). Once we have precalculated all that, we simply iterate from 1 to N and for every number x that we didn’t cross out, we add (or subtract) to our answer.
  • Final observations: We should add 2 to our answer (the two borders). If N = 0, the answer is 1, except M = 0 too, in which case the answer is 0.
  • (This solution idea is from this link )

    
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    
    #define pii              pair <int,int>
    #define pll              pair <long long,long long>
    #define sc               scanf
    #define pf               printf
    #define Pi               2*acos(0.0)
    #define ms(a,b)          memset(a, b, sizeof(a))
    #define pb(a)            push_back(a)
    #define MP               make_pair
    #define db               double
    #define ll               long long
    #define EPS              10E-10
    #define ff               first
    #define ss               second
    #define sqr(x)           (x)*(x)
    #define D(x)             cerr<<#x " = "<<(x)<<endl
    #define VI               vector <int>
    #define DBG              pf("Hi\n")
    #define MOD              1000000007
    #define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    #define SZ(a)            (int)a.size()
    #define sf(a)            scanf("%d",&a)
    #define sfl(a)           scanf("%lld",&a)
    #define sff(a,b)         scanf("%d %d",&a,&b)
    #define sffl(a,b)        scanf("%lld %lld",&a,&b)
    #define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
    #define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
    #define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
    #define loop(i,n)        for(int i=0;i<n;i++)
    #define loop1(i,n)       for(int i=1;i<=n;i++)
    #define REP(i,a,b)       for(int i=a;i<b;i++)
    #define RREP(i,a,b)      for(int i=a;i>=b;i--)
    #define TEST_CASE(t)     for(int z=1;z<=t;z++)
    #define PRINT_CASE       printf("Case %d: ",z)
    #define LINE_PRINT_CASE  printf("Case %d:\n",z)
    #define CASE_PRINT       cout<<"Case "<<z<<": "
    #define all(a)           a.begin(),a.end()
    #define intlim           2147483648
    #define infinity         (1<<28)
    #define ull              unsigned long long
    #define gcd(a, b)        __gcd(a, b)
    #define lcm(a, b)        ((a)*((b)/gcd(a,b)))
    
    using namespace std;
    
    //using namespace __gnu_pbds;
    //typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
    
    
    /*----------------------Graph Moves----------------*/
    //const int fx[]={+1,-1,+0,+0};
    //const int fy[]={+0,+0,+1,-1};
    //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
    //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
    //const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
    //const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
    /*------------------------------------------------*/
    
    /*-----------------------Bitmask------------------*/
    //int Set(int N,int pos){return N=N | (1<<pos);}
    //int reset(int N,int pos){return N= N & ~(1<<pos);}
    //bool check(int N,int pos){return (bool)(N & (1<<pos));}
    /*------------------------------------------------*/
    
    #define mx 1000006
    ll mobius[mx];
    bool vis[mx];
    ll n,m;
    
    void precal()
    {
        for(int i=2;i<mx;)
        {
            for(int j=i+i;j<mx;j+=i)
                mobius[j]++;
            for(++i;;i++)
                if(mobius[i]==0) break;
        }
    
        for(int i=2;i<mx;i++)
        {
            if(mobius[i]==1)
            {
                for(int j=i;j<mx;j+=i)
                    vis[j]=1;
            }
        }
    
    }
    
    int main()
    {
    
    //    freopen("in.txt","r",stdin);
    //	  freopen("out.txt","w",stdout);
    
        int t;
        sf(t);
        precal();
        TEST_CASE(t)
        {
            sffl(n,m);
            if(n>m) swap(n,m);
    
            ll ans=n*m;
    //        ms(mobius,0);
    //        ms(vis,0);
            for(ll i=2;i<=n;i++)
            {
                if(vis[i]==1) continue;
                ll x=(m/i)*(n/i);
                if(mobius[i]==0)
                    ans-=x;
                else if(mobius[i]%2==1)
                    ans-=x;
                else
                    ans+=x;
    //            for(ll j=i;j<=n;j*=i) vis[j]=1;
            }
    
            if(n) ans++;
            if(m) ans++;
            PRINT_CASE;
            printf("%lld\n",ans);
    
        }
    
        return 0;
    }
    
    
    Advertisements

    nCr%m when m is not prime and n and r is sufficiently large.

    In many problems we need to calculate nCr%m where n, r and m are three positive integers. If the mod value m is a prime number then we can calculate nCr%m in different ways like using loops, using pascal’s triangle, using modular multiplicative inverse, using dp technique etc. This ways are described with source codes in this post.

    Now our problem arrive when the mod value m is not prime. In this case we can’t use the above techniques. In this case we need to use the chinese remainder theorem (CRT) and Andrew Granville’s theory for calculating nCr. Here I provide you some ways to learn this techniques. I think this ways will be helpful to you.

    1. First learn about chinese remainder theorem (CRT). You can learn it form these sources-
    a. geeksforgeeks 1
    b. geeksforgeeks 2
    c. youtube 1
    d. youtube 2

    2. Second you can have a look on Andres Granville’s theory. The theory is explained here.

    3. Now you can have a look on this problem. The detailed algorithm for our job is explained in this problem’s editorial section.

    4. Now you can try to implement the algorithm. If you find any difficulties after several tries then you can see my implementation. Which is given below.

    
    #include <bits/stdc++.h>
    
    #define pii              pair <int,int>
    #define pll              pair <long long,long long>
    #define sc               scanf
    #define pf               printf
    #define Pi               2*acos(0.0)
    #define ms(a,b)          memset(a, b, sizeof(a))
    #define pb(a)            push_back(a)
    #define MP               make_pair
    #define db               double
    #define ll               long long
    #define EPS              10E-10
    #define ff               first
    #define ss               second
    #define sqr(x)           (x)*(x)
    #define D(x)             cout<<#x " = "<<(x)<<endl
    #define VI               vector <int>
    #define DBG              pf("Hi\n")
    #define MOD              1000000007
    #define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    #define SZ(a)            (int)a.size()
    #define sf(a)            scanf("%d",&a)
    #define sfl(a)           scanf("%lld",&a)
    #define sff(a,b)         scanf("%d %d",&a,&b)
    #define sffl(a,b)        scanf("%lld %lld",&a,&b)
    #define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
    #define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
    #define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
    #define loop(i,n)        for(int i=0;i<n;i++)
    #define loop1(i,n)       for(int i=1;i<=n;i++)
    #define REP(i,a,b)       for(int i=a;i<b;i++)
    #define RREP(i,a,b)      for(int i=a;i>=b;i--)
    #define TEST_CASE(t)     for(int z=1;z<=t;z++)
    #define PRINT_CASE       printf("Case %d: ",z)
    #define LINE_PRINT_CASE  printf("Case %d:\n",z)
    #define CASE_PRINT       cout<<"Case "<<z<<": "
    #define all(a)           a.begin(),a.end()
    #define intlim           2147483648
    #define infinity         (1<<28)
    #define ull              unsigned long long
    #define gcd(a, b)        __gcd(a, b)
    #define lcm(a, b)        ((a)*((b)/gcd(a,b)))
    
    using namespace std;
    
    
    //----------------------Graph Moves----------------
    //const int fx[]={+1,-1,+0,+0};
    //const int fy[]={+0,+0,+1,-1};
    //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
    //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
    //const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
    //const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
    //------------------------------------------------
    
    //-----------------------Bitmask------------------
    //int Set(int N,int pos){return N=N | (1<<pos);}
    //int reset(int N,int pos){return N= N & ~(1<<pos);}
    //bool check(int N,int pos){return (bool)(N & (1<<pos));}
    //------------------------------------------------
    
    #define mx 1000006
    
    bitset<mx/2>vis;
    vector<int>prime;
    
    vector<pii>factor;
    
    void sieve()
    {
        int x=mx/2,y=sqrt(mx)/2;
        for(int i=1; i<=y; i++)
        {
            if(vis[i]==0)
            {
                for(int j=i*(i+1)*2; j<x; j+=(2*i)+1)
                    vis[j]=1;
            }
        }
    
        prime.pb(2);
    
        for(int i=3; i<mx; i+=2)
            if(vis[i/2]==0)
                prime.pb(i);
    
    }
    
    ll factorial[mx];
    ll arr[mx];
    
    
    vector<ll>ans;
    
    void precal(ll p, ll q, ll mod)
    {
        arr[0]=1;
        arr[1]=1;
    //    ll mod=bigmod(p,q,MOD);
        ll x=1;
        for(ll i=2; i<=mod; i++)
        {
            if(i%p)
                x=i;
            else
                x=1;
            arr[i]=(arr[i-1]*x)%mod;
        }
    }
    
    ll bigmod(ll n, ll p, ll mod)
    {
        ll ret=1;
        while(p)
        {
            if(p%2)
                ret=(ret*n)%mod;
            n=(n*n)%mod;
            p/=2;
        }
        return ret;
    }
    
    ll E(ll n, ll p)
    {
        ll ret=0;
        while(n)
        {
            ret+=n/p;
            n=n/p;
        }
        return ret;
    }
    
    ll f(ll n, ll mod)
    {
        ll ret=bigmod(arr[mod-1],n/mod,mod)*arr[n%mod];
        return ret;
    }
    
    ll F(ll n, ll mod, ll p)
    {
        ll ret=1;
        ll i=1;
        while(i<=n)
        {
            ret=(ret*f(n/i,mod))%mod;
            i=i*p;
        }
        return ret;
    }
    
    int inv(int a, int m) // Calculating Modular Multiplicative Inverse
    {
        int m0 = m, t, q;
        int x0 = 0, x1 = 1;
    
        if (m == 1)
            return 0;
    
    //     Apply extended Euclid Algorithm
        while (a > 1)
        {
    //         q is quotient
            q = a / m;
    
            t = m;
    
    //         m is remainder now, process same as
    //         euclid's algo
            m = a % m, a = t;
    
            t = x0;
    
            x0 = x1 - q * x0;
    
            x1 = t;
        }
    
    //     Make x1 positive
        if (x1 < 0)
            x1 += m0;
    
        return x1;
    }
    
    
    
    
    ll nCr(ll n, ll r, ll p, ll mod)
    {
        ll e=E(n,p)-E(r,p)-E(n-r,p);
        ll mod1=F(n,mod,p);
        ll mod2=(F(r,mod,p)*F(n-r,mod,p))%mod;
        mod2=inv(mod2,mod);
        ll ret=bigmod(p,e,mod);
        ret*=mod1;
        ret%=mod;
        ret*=mod2;
        ret%=mod;
        return ret;
    }
    
    ll findMinX(int k) // Chinese Remainder
    {
        ll prod = 1;
        vector<int>num;
        for(int i=0; i<k; i++)
        {
            num.pb(bigmod(factor[i].ff,factor[i].ss,MOD));
        }
        for (int i = 0; i < k; i++)
            prod *= num[i];
    
        ll result = 0;
    
        for (int i = 0; i < k; i++)
        {
            ll pp = prod / num[i];
            result += ans[i] * inv(pp, num[i]) * pp;
        }
    
        return result % prod;
    }
    
    ll nCr_mod_m(ll n, ll r, ll m)
    {
        factor.clear();
        ans.clear();
        int root=sqrt(m);
        ll mm=m;
        for(int i=0; i<SZ(prime) && prime[i]<=root; i++)
        {
            if(mm%prime[i]==0)
            {
                int cnt=0;
                while(mm%prime[i]==0)
                {
                    mm/=prime[i];
                    cnt++;
                }
                factor.pb(pii(prime[i],cnt));
                root=sqrt(mm);
            }
        }
    
        if(mm>1)
            factor.pb(pii(mm,1));
    
    
    
        for(int i=0; i<SZ(factor); i++)
        {
            ll p=factor[i].ff;
    
            ll num=bigmod(p,factor[i].ss,MOD);
            precal(p,factor[i].ss,num);
            ans.pb(nCr(n,r,p,num));
        }
    
        ll anss=findMinX(SZ(factor));
        return anss;
    }
    
    int main()
    {
    
    //    freopen("in.txt","r",stdin);
    //	  freopen("out.txt","w",stdout);
    
        sieve();
    
        int t;
        sf(t);
        TEST_CASE(t)
        {
            ll n,r,m;
            cin>>n>>r>>m;
    
            ll ans=nCr_mod_m(n,r,m);
    
            pf("%lld C %lld mod %lld = %lld\n",n,r,m,ans);
        }
    
        return 0;
    }
    
    
    

    Practice problems:
    1. nCr
    2. Codechef’s Long Sandwich(SANDWICH).

    UVa 11246 – K-Multiple Free set

    Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2203

    Solution Idea:


    int MFS(int N,int K)
    {
    int ret=0;
    for(int i=1;N;i=-i)
    {
    ret+=N*i;
    N/=K;
    }
    return ret;
    }

    So how does this work? Let us start with the full set {1…N}. We need to remove some numbers from this so that it is a K-multiple free set. For this, let us remove every multiple of K from the set. These are the numbers K,2K… and there are N/K of them. Removing them gives us a K-multiple free set. But we have removed some numbers unnecessarily. Since we already removed K, removing K² was unnecessary. Thus we can put back K²,2K²…, which would be N/K² numbers in total. But this ends up putting both K² and K³ into the set and we need to remove all multiples of K³ now. Proceeding in this fashion, it is easy to see that the cardinality of the final set is N – N/K + N/K² – N/K³…

    In general, an input size of N=10⁹ in a mathematical problem should give you the idea that neither the time or space complexity of the solution can be O(N) and you have to come up with some sort of a closed form solution.

    This solutino idea is from this link.

    
    #include <bits/stdc++.h>
    
    #define pii              pair <int,int>
    #define pll              pair <long long,long long>
    #define sc               scanf
    #define pf               printf
    #define Pi               2*acos(0.0)
    #define ms(a,b)          memset(a, b, sizeof(a))
    #define pb(a)            push_back(a)
    #define MP               make_pair
    #define db               double
    #define ll               long long
    #define EPS              10E-10
    #define ff               first
    #define ss               second
    #define sqr(x)           (x)*(x)
    #define D(x)             cout<<#x " = "<<(x)<<endl
    #define VI               vector <int>
    #define DBG              pf("Hi\n")
    #define MOD              1000000007
    #define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    #define SZ(a)            (int)a.size()
    #define sf(a)            scanf("%d",&a)
    #define sfl(a)           scanf("%lld",&a)
    #define sff(a,b)         scanf("%d %d",&a,&b)
    #define sffl(a,b)        scanf("%lld %lld",&a,&b)
    #define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
    #define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
    #define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
    #define loop(i,n)        for(int i=0;i<n;i++)
    #define loop1(i,n)       for(int i=1;i<=n;i++)
    #define REP(i,a,b)       for(int i=a;i<b;i++)
    #define RREP(i,a,b)      for(int i=a;i>=b;i--)
    #define TEST_CASE(t)     for(int z=1;z<=t;z++)
    #define PRINT_CASE       printf("Case %d: ",z)
    #define LINE_PRINT_CASE  printf("Case %d:\n",z)
    #define CASE_PRINT       cout<<"Case "<<z<<": "
    #define all(a)           a.begin(),a.end()
    #define intlim           2147483648
    #define infinity         (1<<28)
    #define ull              unsigned long long
    #define gcd(a, b)        __gcd(a, b)
    #define lcm(a, b)        ((a)*((b)/gcd(a,b)))
    
    using namespace std;
    
    
    /*----------------------Graph Moves----------------*/
    //const int fx[]={+1,-1,+0,+0};
    //const int fy[]={+0,+0,+1,-1};
    //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
    //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
    //const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
    //const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
    /*------------------------------------------------*/
    
    /*-----------------------Bitmask------------------*/
    //int Set(int N,int pos){return N=N | (1<<pos);}
    //int reset(int N,int pos){return N= N & ~(1<<pos);}
    //bool check(int N,int pos){return (bool)(N & (1<<pos));}
    /*------------------------------------------------*/
    
    
    int main()
    {
    
    //    freopen("in.txt","r",stdin);
    //	  freopen("out.txt","w",stdout);
    
        int t;
        sf(t);
        TEST_CASE(t)
        {
            ll n,k;
            sffl(n,k);
            if(k==0)
                pf("0\n");
            else
            {
                ll ans=n;
                ll kk=k;
                int cnt=1;
                while(kk<=n)
                {
                    if(cnt%2)
                        ans-=(n/kk);
                    else
                        ans+=(n/kk);
                    kk*=k;
                    cnt++;
                }
                pf("%lld\n",ans);
            }
        }
    
        return 0;
    }
    
    

    Light OJ: 1326 – Race

    Problem Link : http://lightoj.com:81/volume/problem/1326

    Solution Idea:

    Let’s define dp(i) as the number of ways in which a race with “i” horses can finish.

    Suppose we have “i” horses at the race and we will choose k of them for the first place, leaving “i – k” for the second (or higher) place. The process to count the number of ways to choose horses for the second place is equals to the original problem. This is the reason why we use dp.

    (This Solution idea is from Manuel Pinda)

    
    #include <bits/stdc++.h>
    
    #define pii              pair <int,int>
    #define pll              pair <long long,long long>
    #define sc               scanf
    #define pf               printf
    #define Pi               2*acos(0.0)
    #define ms(a,b)          memset(a, b, sizeof(a))
    #define pb(a)            push_back(a)
    #define MP               make_pair
    #define db               double
    #define ll               long long
    #define EPS              10E-10
    #define ff               first
    #define ss               second
    #define sqr(x)           (x)*(x)
    #define D(x)             cout<<#x " = "<<(x)<<endl
    #define VI               vector <int>
    #define DBG              pf("Hi\n")
    #define MOD              10056
    #define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    #define SZ(a)            (int)a.size()
    #define sf(a)            scanf("%d",&a)
    #define sfl(a)           scanf("%lld",&a)
    #define sff(a,b)         scanf("%d %d",&a,&b)
    #define sffl(a,b)        scanf("%lld %lld",&a,&b)
    #define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
    #define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
    #define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
    #define loop(i,n)        for(int i=0;i<n;i++)
    #define loop1(i,n)       for(int i=1;i<=n;i++)
    #define REP(i,a,b)       for(int i=a;i<b;i++)
    #define RREP(i,a,b)      for(int i=a;i>=b;i--)
    #define TEST_CASE(t)     for(int z=1;z<=t;z++)
    #define PRINT_CASE       printf("Case %d: ",z)
    #define LINE_PRINT_CASE  printf("Case %d:\n",z)
    #define CASE_PRINT       cout<<"Case "<<z<<": "
    #define all(a)           a.begin(),a.end()
    #define intlim           2147483648
    #define infinity         (1<<28)
    #define ull              unsigned long long
    #define gcd(a, b)        __gcd(a, b)
    #define lcm(a, b)        ((a)*((b)/gcd(a,b)))
    
    using namespace std;
    
    
    /*----------------------Graph Moves----------------*/
    //const int fx[]={+1,-1,+0,+0};
    //const int fy[]={+0,+0,+1,-1};
    //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
    //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
    //const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
    //const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
    /*------------------------------------------------*/
    
    /*-----------------------Bitmask------------------*/
    //int Set(int N,int pos){return N=N | (1<<pos);}
    //int reset(int N,int pos){return N= N & ~(1<<pos);}
    //bool check(int N,int pos){return (bool)(N & (1<<pos));}
    /*------------------------------------------------*/
    
    ll dp[1003][1003];
    ll ans[1003];
    
    ll nCr(int n, int r)
    {
        if(r==1) return n;
        if(n==r) return 1;
    
        ll &ret=dp[n][r];
    
        if(ret!=-1) return ret;
    
        return ret=(nCr(n-1,r-1)%MOD+nCr(n-1,r)%MOD)%MOD;
    }
    
    ll func(int n)
    {
        if(n==0) return 1;
        if(ans[n]!=-1) return ans[n];
    
        ll ret=0;
    
        for(int i=1;i<=n;i++)
        {
            ret+=(nCr(n,i)*func(n-i))%MOD;
            ret%=MOD;
        }
    
        return ans[n]=ret;
    }
    
    int main()
    {
    
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
    
        int t;
        sf(t);
    
        ms(dp,-1);
        ms(ans,-1);
    
        TEST_CASE(t)
        {
            int n;
            sf(n);
            PRINT_CASE;
    
            printf("%lld\n",func(n));
    
        }
    
        return 0;
    }
    
    
    

    Light OJ: 1102 – Problem Makes Problem

    Problem Link : http://lightoj.com:81/volume/problem/1102

    
    #include <bits/stdc++.h>
    
    #define pii              pair <int,int>
    #define pll              pair <long long,long long>
    #define sc               scanf
    #define pf               printf
    #define Pi               2*acos(0.0)
    #define ms(a,b)          memset(a, b, sizeof(a))
    #define pb(a)            push_back(a)
    #define MP               make_pair
    #define db               double
    #define ll               long long
    #define EPS              10E-10
    #define ff               first
    #define ss               second
    #define sqr(x)           (x)*(x)
    #define D(x)             cout<<#x " = "<<(x)<<endl
    #define VI               vector <int>
    #define DBG              pf("Hi\n")
    #define MOD              1000000007
    #define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    #define SZ(a)            (int)a.size()
    #define sf(a)            scanf("%d",&a)
    #define sfl(a)           scanf("%lld",&a)
    #define sff(a,b)         scanf("%d %d",&a,&b)
    #define sffl(a,b)        scanf("%lld %lld",&a,&b)
    #define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
    #define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
    #define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
    #define loop(i,n)        for(int i=0;i<n;i++)
    #define loop1(i,n)       for(int i=1;i<=n;i++)
    #define REP(i,a,b)       for(int i=a;i<b;i++)
    #define RREP(i,a,b)      for(int i=a;i>=b;i--)
    #define TEST_CASE(t)     for(int z=1;z<=t;z++)
    #define PRINT_CASE       printf("Case %d: ",z)
    #define LINE_PRINT_CASE  printf("Case %d:\n",z)
    #define CASE_PRINT       cout<<"Case "<<z<<": "
    #define all(a)           a.begin(),a.end()
    #define intlim           2147483648
    #define infinity         (1<<28)
    #define ull              unsigned long long
    #define gcd(a, b)        __gcd(a, b)
    #define lcm(a, b)        ((a)*((b)/gcd(a,b)))
    
    using namespace std;
    
    
    /*----------------------Graph Moves----------------*/
    //const int fx[]={+1,-1,+0,+0};
    //const int fy[]={+0,+0,+1,-1};
    //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
    //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
    //const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
    //const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
    /*------------------------------------------------*/
    
    /*-----------------------Bitmask------------------*/
    //int Set(int N,int pos){return N=N | (1<<pos);}
    //int reset(int N,int pos){return N= N & ~(1<<pos);}
    //bool check(int N,int pos){return (bool)(N & (1<<pos));}
    /*------------------------------------------------*/
    
    ll fact[2000006];
    
    ll bigmod(ll n, ll pow)
    {
        ll ret=1;
        while(pow)
        {
            if(pow%2==1)
                {ret*=n; ret%=MOD;}
            n*=n;
            n%=MOD;
            pow/=2;
    
        }
        return ret;
    }
    
    int main()
    {
    
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        fact[0]=1;
        for(ll i=1;i<2000005;i++)
        {
            fact[i]=(fact[i-1]*i)%MOD;
        }
    
        int t;
        sf(t);
        TEST_CASE(t)
        {
            int n,k;
    
            sff(n,k);
    
            ll down=(fact[k-1]*fact[n])%MOD;
    
            down=bigmod(down,MOD-2);
    
            down=(fact[n+k-1]*down)%MOD;
    
            PRINT_CASE;
    
            printf("%lld\n",down);
    
    
    
        }
    
        return 0;
    }
    
    

    Light OJ: 1095 – Arrange the Numbers

    Problem Link : http://lightoj.com:81/volume/problem/1095

    
    #include <bits/stdc++.h>
    
    #define pii              pair <int,int>
    #define pll              pair <long long,long long>
    #define sc               scanf
    #define pf               printf
    #define Pi               2*acos(0.0)
    #define ms(a,b)          memset(a, b, sizeof(a))
    #define pb(a)            push_back(a)
    #define MP               make_pair
    #define db               double
    #define ll               long long
    #define EPS              10E-10
    #define ff               first
    #define ss               second
    #define sqr(x)           (x)*(x)
    #define D(x)             cout<<#x " = "<<(x)<<endl
    #define VI               vector <int>
    #define DBG              pf("Hi\n")
    #define MOD              1000000007
    #define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    #define SZ(a)            (int)a.size()
    #define sf(a)            scanf("%d",&a)
    #define sfl(a)           scanf("%lld",&a)
    #define sff(a,b)         scanf("%d %d",&a,&b)
    #define sffl(a,b)        scanf("%lld %lld",&a,&b)
    #define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
    #define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
    #define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
    #define loop(i,n)        for(int i=0;i<n;i++)
    #define loop1(i,n)       for(int i=1;i<=n;i++)
    #define REP(i,a,b)       for(int i=a;i<b;i++)
    #define RREP(i,a,b)      for(int i=a;i>=b;i--)
    #define TEST_CASE(t)     for(int z=1;z<=t;z++)
    #define PRINT_CASE       printf("Case %d: ",z)
    #define LINE_PRINT_CASE  printf("Case %d:\n",z)
    #define CASE_PRINT       cout<<"Case "<<z<<": "
    #define all(a)           a.begin(),a.end()
    #define intlim           2147483648
    #define infinity         (1<<28)
    #define ull              unsigned long long
    #define gcd(a, b)        __gcd(a, b)
    #define lcm(a, b)        ((a)*((b)/gcd(a,b)))
    
    using namespace std;
    
    
    /*----------------------Graph Moves----------------*/
    //const int fx[]={+1,-1,+0,+0};
    //const int fy[]={+0,+0,+1,-1};
    //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
    //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
    //const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
    //const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
    /*------------------------------------------------*/
    
    /*-----------------------Bitmask------------------*/
    //int Set(int N,int pos){return N=N | (1<<pos);}
    //int reset(int N,int pos){return N= N & ~(1<<pos);}
    //bool check(int N,int pos){return (bool)(N & (1<<pos));}
    /*------------------------------------------------*/
    
    ll fact[1005];
    
    ll dp[1005][1005];
    
    ll nCk(int n, int k)
    {
        if(k==1) return n;
        if(n==k) return 1;
    
        if(dp[n][k]!=-1) return dp[n][k];
    
        return dp[n][k]= (nCk(n-1,k-1)+nCk(n-1,k))%MOD;
    }
    
    
    int main()
    {
    
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
    
        fact[0]=1;
    
        for(ll i=1; i<1002; i++) fact[i]=(fact[i-1]*i)%MOD;
    
        int t;
        sf(t);
        ms(dp,-1);
    
        TEST_CASE(t)
        {
            ll n,m,k;
            sfffl(n,m,k);
            ll ans=nCk(m,k);
    
            int nn=n-k;
    
            ll ans1=fact[n-k];
    
            for(int i=1; i<=(m-k); i++)
            {
                if(i%2==1)
                    ans1-= (nCk(m-k,i)*fact[nn-i])%MOD;
                else
                    ans1+= (nCk(m-k,i)*fact[nn-i])%MOD;
                ans1=(ans1+MOD)%MOD;
            }
    
            PRINT_CASE;
    
            printf("%lld\n",(ans*ans1)%MOD);
    
    
        }
    
    
        return 0;
    }