Advertisement
Guest User

Untitled

a guest
Apr 21st, 2021
1,202
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MX 200
  4. #define mod 1000000007
  5. long long inv[MX+5];
  6. long long ncr(int n,int r)
  7. {
  8.     long long ret=1;
  9.     for (int i=n-r+1;i<=n;i++)
  10.     ret=(ret*i)%mod;
  11.     for (int i=1;i<=r;i++)
  12.     ret=(ret*inv[i])%mod;
  13.     return ret;
  14. }
  15. int main()
  16. {
  17.     inv[1]=1;
  18.     for (int i=2;i<=MX;i++)
  19.     inv[i]=inv[mod%i]*(mod-mod/i)%mod;
  20.     int n,k;
  21.     scanf("%d%d",&n,&k);
  22.     vector<long long> dp(k+1,0);
  23.     dp[0]=1;
  24.     int curn=1;
  25.     for (int i=30-__builtin_clz(n);i>=0;i--)
  26.     {
  27.         vector<long long> big(k+1,0),pw(k+1),tmp(k+1,0);
  28.         pw[0]=1;
  29.         for (int j=1;j<=k;j++)
  30.         pw[j]=(curn*pw[j-1])%mod;
  31.         for (int j=0;j<=min(k,curn);j++)
  32.         {
  33.             for (int l=0;l<=j;l++)
  34.             big[j]=(big[j]+ncr(curn-l,j-l)*dp[l]%mod*pw[j-l])%mod;
  35.         }
  36.         for (int js=0;js<=k;js++)
  37.         {
  38.             for (int jb=0;jb<=k;jb++)
  39.             {
  40.                 if (js+jb<=k)
  41.                 tmp[js+jb]=(tmp[js+jb]+dp[js]*big[jb])%mod;
  42.             }
  43.         }
  44.         dp=tmp;
  45.         curn*=2;
  46.         if (n&(1<<i))
  47.         {
  48.             vector<long long> tmp(k+1);
  49.             tmp[0]=1;
  50.             for (int j=1;j<=k;j++)
  51.             tmp[j]=(dp[j]+curn*dp[j-1])%mod;
  52.             dp=tmp;
  53.             curn++;
  54.         }
  55.     }
  56.     int ans[]={1,0};
  57.     for (int j=1;j<=k;j++)
  58.     {
  59.         ans[j%2]=(ans[j%2]+dp[j])%mod;
  60.         printf("%d ",ans[j%2]);
  61.     }
  62.     printf("\n");
  63. }
  64.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement