noi.ac day5t1 count-白红宇

noi.ac day5t1 count

阅读量：6464 次

发布时间：2019-06-23

本文共 985 字，大约阅读时间需要 3 分钟。

分析

首先一个很重要的性质是每个数至少出现一次

所以只有一个数会出现两次

我们只需要求出n+1个数选k个数的方案数再减去重复的部分即可

重复部分于两个相同数中间的距离有关，详见代码

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const int mod = 1e9+7;int p[100100];inline int pw(int x,int p){ x%=mod; int res=1; while(p){ if(p&1)res=(long long)res*x%mod; x=(long long)x*x%mod; p>>=1; } return res;}inline int c(int n,int m){ if(m>n)return 0; return (long long)p[n]*pw(p[m],mod-2)%mod*pw(p[n-m],mod-2)%mod;}int sum[100100],a[100100];int main(){ int n,m,i,j,k,wh; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&a[i]); if(sum[a[i]])wh=i-sum[a[i]]; sum[a[i]]=i; } p[0]=p[1]=1; for(i=2;i<=n+1;i++)p[i]=(long long)p[i-1]*i%mod; for(k=1;k<=n+1;k++) printf("%d\n",(c(n+1,k)-c(n-wh,k-1)+mod)%mod); return 0;}