SHARE
TWEET

Untitled

a guest Jun 3rd, 2019 737 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. using namespace std;
  3. #define mod 1000000007
  4. int n,dp[1000005][21][2];
  5. int f(int x,int y)
  6. {
  7.     int tmp=(1<<x);
  8.     if (y)
  9.     tmp*=3;
  10.     return n/tmp;
  11. }
  12. int main()
  13. {
  14.     scanf("%d",&n);
  15.     int p=0;
  16.     while ((1<<p)<=n)
  17.     p++;
  18.     p--;
  19.     dp[1][p][0]=1;
  20.     if ((1<<(p-1))*3<=n)
  21.     dp[1][p-1][1]=1;
  22.     for (int i=1;i<n;i++)
  23.     {
  24.         for (int x=0;x<=p;x++)
  25.         {
  26.             for (int y=0;y<=1;y++)
  27.             {
  28.                 dp[i+1][x][y]=(dp[i+1][x][y]+1LL*dp[i][x][y]*(f(x,y)-i))%mod;
  29.                 if (x)
  30.                 dp[i+1][x-1][y]=(dp[i+1][x-1][y]+1LL*dp[i][x][y]*(f(x-1,y)-f(x,y)))%mod;
  31.                 if (y)
  32.                 dp[i+1][x][y-1]=(dp[i+1][x][y-1]+1LL*dp[i][x][y]*(f(x,y-1)-f(x,y)))%mod;
  33.             }
  34.         }
  35.     }
  36.     printf("%d",dp[n][0][0]);
  37. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top