noi.ac #45

题目链接

\(Solution:\)

对于每个\(k\):
不考虑重复，显然为\(C_{n+1}^k\)
现在我们来排除重复的情况，不妨设\(a_{i+1}=a_{j-1}\)，
而重复的情况出现当且仅当\(a_{i+1}\)或\(a_{j-1}\)被挑选
即在\(i+j\)(\([1,i]\)和\([j,n]\))个元素中选取\(k-1\)个，所以排除的情况有\(C_{i+j}^{k-1}\)中
所以答案即为\(C_{n+1}^k-C_{i+j}^{k-1}\)
这里我们使用费马小定理求逆元，再枚举每个\(k\)，即可在线性时间内出解

\(Code:\)

#include<bits/stdc++.h>
using namespace std;
namespace my_std
{
    typedef long long ll;
    #define fr(i,x,y) for(ll i=(x);i<=(y);i++)
    #define enter putchar('\n') 
    inline ll read()
    {
        ll sum=0,f=1;
        char ch=0;
        while(!isdigit(ch))
        {
            if(ch=='-') f=-1;
            ch=getchar();
        }
        while(isdigit(ch))
        {
            sum=(sum<<1)+(sum<<3)+(ch^48);
            ch=getchar();
        }
        return sum*f;
    }
    inline void write(ll x)
    {
        if(x<0)
        {
            putchar('-');
            x=-x;
        }
        if(x>9) write(x/10);
        putchar(x%10+'0');
    }
}
using namespace my_std;
const ll N=1e5+50,mod=1e9+7;
ll n,ii,jj,vis[N],pos[N],mul[N],inv[N];
inline ll C(ll n,ll m)
{
    if(m>n) return 0;
    ll res=inv[m]*inv[n-m]%mod;
    res=res*mul[n]%mod;
    return res;
}
inline ll ksmod(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
inline void cal_inv()
{
    mul[0]=inv[0]=1;
    for(ll i=1;i<=N;i++) mul[i]=mul[i-1]*i%mod;
    inv[N]=ksmod(mul[N],mod-2);
    for(ll i=N-1;i;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int main(void)
{
    cal_inv();
    n=read();
    fr(i,1,n+1)
    {
        ll x=read();
        if(vis[x]) 
        {
            jj=n+1-i;
            ii=pos[x]-1;
            break;
        }
        else
        {
            pos[x]=i;
            vis[x]=1;
        }
    }
    fr(i,1,n+1)
    {
        ll c1=C(n+1,i),c2=C(ii+jj,i-1),ans;
        ans=c1-c2;
        if(ans<0) ans+=mod;
        write(ans);
        enter;
    }
    return 0;
}

noi.ac #45

原文：https://www.cnblogs.com/lgj-lgj/p/12336661.html