Saturday 29 July 2017

Lightoj 1095 - Arrange the Numbers

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MOD 1000000007
  4. #define N 1005
  5. #define ll long long unsigned
  6. ll fac[N];
  7. ll dp[N][N];
  8. int pre(){
  9.     fac[0] = 1;
  10.     for(int i = 1; i <N; i++) fac[i]= (fac[i-1]*i)%MOD;
  11.     memset(dp, -1sizeof(dp));
  12. }
  13. ll ncr(int n, int k){
  14.     if(k==1) return n;
  15.     if(n==k) return 1;
  16.     if(dp[n][k]!=-1) return dp[n][k];
  17.     return dp[n][k]= (ncr(n-1,k-1)+ncr(n-1,k))%MOD;
  18. }
  19. int main(){
  20.     pre();
  21.     int ts;
  22.     scanf("%d"&ts);
  23.     for(int p =1;<= ts; p++){
  24.     int n, m, k;
  25.     scanf("%d%d%d"&n, &m, &k);
  26.     ll ans1 = ncr(m, k);
  27.     ll ans2 = fac[n-k];
  28.     for(int i = 1; i <= m-k; i++){
  29.         if(i%2) ans2-= (ncr(m-k, i)*fac[n-k-i])%MOD;
  30.         else ans2+= (ncr(m-k, i)*fac[n-k-i])%MOD;
  31.         ans2 = (ans2+MOD)%MOD;
  32.     }
  33.     printf("Case %d: %llu\n",p, (ans1*ans2)%MOD);
  34.     }
  35.     return 0;  
  36. }

No comments:

Post a Comment

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...