https://codeforces.com/contest/1174/problem/E

题意：定义gi是排列p1,p2...pi的的GCD（长度为i的前缀GCD）,f(p)是 g1,g2..gn中独特的元素个数

让fmax(n) 成为f(p)在所有整数1,2...n的排列中的最大值，给出整数n，给出满足f(p)=fmax(n)的排列个数 mod(1e9+7)

思路：略

#include <iostream>
using namespace std;
#define mod 1000000007
int n,dp[1000005][21][2];
int f(int x,int y)
{
    int tmp=(1<<x);
    if (y)
    tmp*=3;
    return n/tmp;
}
int main()
{
    scanf("%d",&n);
    int p=0;
    while ((1<<p)<=n)
    p++;
    p--;
    dp[1][p][0]=1;
    if ((1<<(p-1))*3<=n)
    dp[1][p-1][1]=1;
    for (int i=1;i<n;i++)
    {
        for (int x=0;x<=p;x++)
        {
            for (int y=0;y<=1;y++)
            {
                dp[i+1][x][y]=(dp[i+1][x][y]+1LL*dp[i][x][y]*(f(x,y)-i))%mod;
                if (x)
                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;
                if (y)
                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;
            }
        }
    }
    printf("%d",dp[n][0][0]);
}