fork(2) download
copy 
  1.     //#pragma GCC optimize("Ofast,no-stack-protector")
  2.     //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  3.     //#pragma GCC target("avx,tune=native")
  4.     // Anand Jaisingh
  5.  
  6.     #include<bits/stdc++.h>
  7.  
  8.     using namespace std;
  9.  
  10.     typedef complex<double> base;
  11.     typedef long double ld;
  12.     typedef long long ll;
  13.  
  14.     #define pb push_back
  15.     #define pii pair<int,int>
  16.     #define pll pair< ll , ll >
  17.     #define vi vector<int>
  18.     #define vvi vector< vi >
  19.  
  20.     const int maxn=(int)(1e3+5);
  21.     const ll mod=(ll)(1e9+7);
  22.     int fact[maxn],inv_fact[maxn];
  23.     int f[maxn][maxn];
  24.  
  25.     inline int mul(ll a,ll b)
  26.     {
  27.         return (a*b)%mod;
  28.     }
  29.  
  30.     inline int add(int a,int b)
  31.     {
  32.         int ret=a+b;
  33.  
  34.         if(ret>=mod)
  35.         {
  36.             ret-=mod;
  37.         }
  38.  
  39.         return ret;
  40.     }
  41.  
  42.     inline int sub(int a,int b)
  43.     {
  44.         int ret=a-b;
  45.  
  46.         if(ret<0)
  47.         {
  48.             ret+=mod;
  49.         }
  50.  
  51.         return ret;
  52.     }
  53.  
  54.     inline int poww(ll a,ll b)
  55.     {
  56.         int x=1,y=a;
  57.  
  58.         while(b>0)
  59.         {
  60.             if(b%2)
  61.             {
  62.                 x=mul(x,y);
  63.             }
  64.  
  65.             y=mul(y,y);b/=2;
  66.         }
  67.  
  68.         return (int)(x%mod);
  69.     }
  70.  
  71.  
  72.     void build()
  73.     {
  74.         f[1][0]=2;
  75.  
  76.         for(int i=2;i<maxn;i++)
  77.         {
  78.             f[i][0]=2;
  79.  
  80.             for(int j=1;j<maxn;j++)
  81.             {
  82.                 f[i][j]=add(f[i-1][j],f[i-1][j-1]);
  83.             }
  84.         }
  85.  
  86.         fact[0]=1;
  87.  
  88.         for(int i=1;i<maxn;i++)
  89.         {
  90.             fact[i]=mul(fact[i-1],i);
  91.         }
  92.  
  93.         inv_fact[maxn-1]=poww(fact[maxn-1],mod-2);
  94.  
  95.         for(int i=maxn-2;i>=0;i--)
  96.         {
  97.             inv_fact[i]=mul(inv_fact[i+1],i+1);
  98.         }
  99.     }
  100.  
  101.     int C(int n,int r)
  102.     {
  103.         if(n<r)
  104.         {
  105.             return 0;
  106.         }
  107.  
  108.         int lower=n-r,curr=1;
  109.  
  110.         while(n>lower)
  111.         {
  112.             curr=mul(curr,n);
  113.  
  114.             n--;
  115.         }
  116.  
  117.         return mul(curr,inv_fact[r]);
  118.     }
  119.  
  120.     int main()
  121.     {
  122.         ios_base::sync_with_stdio(0);cin.tie(0);
  123.  
  124.         build();int t;cin>>t;
  125.  
  126.         while(t>0)
  127.         {
  128.             int n,k,res=0;cin>>n>>k;
  129.  
  130.             for(int i=0;i<k;i++)
  131.             {
  132.              //   cout<<f[k][i]<<endl;
  133.  
  134.                 int now=mul(f[k][i],C(n-i,k));
  135.  
  136.                 res=add(res,now);
  137.             }
  138.  
  139.             cout<<res<<endl;t--;
  140.         }
  141.  
  142.         return 0;
  143.     }
  144.  
Runtime error #stdin #stdout 0s 19192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pDcORE
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!