[CF][补题][递推计数][DP] codeforces 1043F Make It One

其实我用了一种操蛋的贪心试了一下，所有的cf测试数据里只有一组会错。。但是还没有搞明白为什么错了，也没有办法再继续证明正确性，所以还是放弃了去看tutorial，发现果然没思路就是dp。。。

然后这又不是一个正常的dp，甚至可以说不算是dp吧。。要从一堆数字里选出来一个集合使得gcd为1。确实，涉及到集合就很难操作。但是可以发现，如果这个集合存在，他的size是很小的，这里可以作为一个突破点去想。如果考虑枚举集合的大小，是否能有简单的计算方法。现在需要求的东西可以转化为，是否存在至少一个集合使得他的size为i然后gcd为1，当然这个也不好直接算，但如果再加一维，再枚举gcd，看看会不会有进展：这时候要求的转化为，是否存在至少一个集合，size为i，gcd为j。可以设一个dp[i][j]表示这种集合的数量，然后尝试是否可以递推。这时候可以发现这i个数字一定是从j的倍数里选出来的，所有的选法有C(cntj,i)种，其中cntj是原数列中j的倍数的数量。而这些里面又有一些不符合要求的，是因为他们的gcd=k*j，然后可以发现这些不符合要求的数量就是dp[i][k*j]，这就实现了从大问题往小问题推的转移了。。。然后就只剩下边界的问题了，这个边界也很有意思：因为只考虑k*j<=max(ai)的gcd，所以大于的就是0就可以了

#include

using namespace std;
typedef long long LL;
const int maxn=3e5+5;
const LL mod=1e9+7;

LL dp[15][maxn];
int cnt[maxn];
LL ni[maxn],inv[maxn];

int pof(LL a,int b)
{
    LL ret=1;
    while(b)
    {
        if(b&1)
            ret=(ret*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ret;
}

void sub(LL &a,LL b)
{
    a-=b;
    if(a<0)
        a+=mod;
}

LL C(LL a,LL b)
{
    if(b<0||a>n;
    ni[0]=1;
    for(int i=1; i<=n; i++)
        ni[i]=(ni[i-1]*i)%mod;
    inv[n]=pof(ni[n],mod-2);
    for(int i=n-1;i>=0;i--)
        inv[i]=(inv[i+1]*(i+1))%mod;
    int tmp,mx=0;
    for(int i=1;i<=n;i++)
    {
        cin>>tmp;
        cnt[tmp]++;
        mx=max(mx,tmp);
    }
    for(int i=1;i<=mx;i++)//nice trick
        for(int j=i+i;j<=mx;j+=i)
    {
        cnt[i]+=cnt[j];
    }
    for(int i=1;i<=10;i++)
    {
        for(int j=mx;j>0;j--)
        {
            dp[i][j]=C(cnt[j],i);
            for(LL k=2;k*j<=mx;k++)
                sub(dp[i][j],dp[i][k*j]);
        }
        if(dp[i][1]>0)
        {
            cout<