Advertisement
Guest User

Untitled

a guest
Apr 21st, 2021
1,657
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mod 1000000007
  4. long long ncr[405][405],inv[405],dp[405][405];
  5. long long big_ncr(int n,int r)
  6. {
  7.     long long ret=1;
  8.     for (int i=n-r+1;i<=n;i++)
  9.     ret=(ret*i)%mod;
  10.     for (int i=1;i<=r;i++)
  11.     ret=(ret*inv[i])%mod;
  12.     return ret;
  13. }
  14. int main()
  15. {
  16.     int n,k;
  17.     scanf("%d%d",&n,&k);
  18.     ncr[0][0]=1;
  19.     for (int i=1;i<=2*k;i++)
  20.     {
  21.         dp[i][0]=1;
  22.         ncr[i][0]=1;
  23.         for (int j=1;j<=2*k;j++)
  24.         {
  25.             dp[i][j]=(dp[i-1][j]+(i-1)*dp[i-1][j-1])%mod;
  26.             ncr[i][j]=(ncr[i-1][j]+ncr[i-1][j-1])%mod;
  27.         }
  28.     }
  29.     inv[1]=1;
  30.     for (int i=2;i<=2*k;i++)
  31.     inv[i]=inv[mod%i]*(mod-mod/i)%mod;
  32.     int ans[]={1,0};
  33.     for (int j=1;j<=k;j++)
  34.     {
  35.         for (int i=1;i<=min(n,2*j);i++)
  36.         {
  37.             int cnt=0;
  38.             for (int f=0;f<=i;f++)
  39.             cnt=(cnt+(f%2? -1:1)*ncr[i][f]*dp[i-f][j]%mod+mod)%mod;
  40.             ans[j%2]=(ans[j%2]+big_ncr(n,i)*cnt)%mod;
  41.         }
  42.         printf("%d ",ans[j%2]);
  43.     }
  44. }
  45.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement