直接上题解

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define ll long long 7 const int Mod=1000000009,N=3000; 8 ll jc[N+10],jcny[N+10],jcnys[N+10],K[N+10],p[N+10],f[N+10]; 9 int read(){10     int t=0,f=1;char ch=getchar();11     while (ch<'0'||ch>'9'){
   if (ch=='-')f=-1;ch=getchar();}12     while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}13     return t*f;14 }15 int Pow(int a,int n){16     int res=1;17     while (n){18         if (n%2) res=((ll)res*a)%Mod;19         a=((ll)a*a)%Mod;20         n/=2;21     }22     return res;23 }24 int main(){25     jc[0]=1;26     for (int i=1;i<=3000;i++) jc[i]=(ll)(jc[i-1]*i)%Mod;27     jcny[3000]=Pow(jc[3000],Mod-2)%Mod;28     for (int i=2999;i>=0;i--) jcny[i]=(ll)jcny[i+1]*(i+1)%Mod;29     for (int i=0;i<=3000;i++) jcnys[i]=(ll)jcny[i]*jcny[i]%Mod;30     for (int i=0;i<=3000;i++)31      if ((i&1)&&jcny[i]) K[i]=Mod-jcny[i];else K[i]=jcny[i];32     int n=read();33     for (int i=1;i<=n;i++) {34         int x=read();p[x]++;35     } 36     f[0]=1;37     for (int k=1,tot=0;k<=n;k++){38         if (p[k]==0) continue;39         tot+=p[k];40         for (int i=tot;i>=0;i--){41             f[i]=(ll)f[i]*jcnys[p[k]]%Mod;42             for (int j=1;j<=p[k]&&j<=i;j++)43              f[i]=((ll)f[i-j]*K[j]%Mod*jcnys[p[k]-j]+f[i])%Mod;44         }45     }46     ll ans=0;47     for (int i=0;i<=n;i++)48      ans=((ll)jc[n-i]*f[i]+ans)%Mod;49     for (int i=1;i<=n;i++)50      ans=(ll)ans*jc[p[i]]%Mod;51     printf("%I64d\n",ans); 52 }