Author: hi Language: cpp
Description: Not specified Timestamp: 2017-08-01 06:19:52 +0000
View raw paste Reply
  1. #include <iostream>
  2. #include <vector>
  3. #define MOD 1000000009
  4. using namespace std;
  5.  
  6. int main() {
  7.         long t, n, r;
  8.         cin >> t;
  9.         while(t--) {
  10.             cin >> n >> r;
  11.             if(n < r) cout << 0 << endl;
  12.             else {
  13.                 vector<long> ncr;
  14.                 ncr.push_back(1);
  15.                 long r1 = 1;
  16.                 while(r1 <= r && r1 <= n/2) {
  17.                     long m = (n-r1+1)/r1;
  18.                     ncr.push_back((m*ncr[r1-1])%MOD);
  19.                     r1++;
  20.                 }
  21.                 while(r1 <= r) {
  22.                     ncr.push_back(ncr[n-r1]);
  23.                     r1++;
  24.                 }
  25.                 cout << ncr[r]%MOD << endl;
  26.             }
  27.         }
  28.         return 0;
  29. }
View raw paste Reply