容斥

NC15079 大水题

模板题

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL a[5]={0,2,5,11,13};
int main()
{
    LL n;
    while(scanf("%lld",&n)!=EOF)
    {
        LL ans=n;
        for(int i=1,cnt=0;i<=15;++i,cnt=0)
        {
            int tot=i,j=0;
            LL tmp=1;
            while(tot)
            {
                ++j;
                if(tot&1)
                {
                    ++cnt;
                    tmp*=a[j];
                }
                tot>>=1;
            }
            if(cnt&1)ans-=n/tmp;
            else ans+=n/tmp;
        }
        printf("%lld\n",ans);
    }
}

NC19857 最后的晚餐(dinner)

正难则反

求有i对相邻的方案数

至少0对相邻的-至少1对相邻的+至少2对相邻的-......

i对相邻的方案数是(2^i)*C(n,i)*(2*n-i)!

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL mod=1000000007;
int f[30000005],invf[30000005];
int ksm(int x,int k)
{
    int s=1;
    while(k)
    {
        if(k&1)    s=1LL*s*x%mod;
        k>>=1;
        x=1LL*x*x%mod;
    }
    return s%mod;
}
int C(int n,int m)
{
    return 1LL*f[n]*1LL*invf[m]%mod*1LL*invf[n-m]%mod;
}
int main()
{
    LL n;scanf("%lld",&n);
    if(n==0||n==1){printf("0");return 0;}
    f[0]=1;
    for(register int i=1;i<=3e7;++i)f[i]=1LL*f[i-1]*i%mod;
    invf[30000000]=ksm(f[30000000],mod-2);
    for(int i=3e7-1;i>=0;--i)invf[i]=1LL*invf[i+1]*(i+1)%mod;
    
    int p=1;//2的i次幂.
    LL jc=f[n-1];
    p=ksm(2,n);
    LL ans=0;
    for(register int i=n;i>=0;--i)
    {
        if(i&1) ans=(1LL*ans-1LL*p*C(n,i)%mod*1LL*jc%mod+mod)%mod;
        else    ans=(1LL*ans+1LL*p*C(n,i)%mod*1LL*jc%mod+mod)%mod;
        jc=jc*(2*n-i)%mod;
        p=1LL*p*invf[2]%mod;
    }
    printf("%lld\n",ans);
}

评价是卡常最后10分过不去。。。。