P4491 [HAOI2018] 染色-白红宇的个人博客

P4491 [HAOI2018] 染色

发布日期：2025-05-01 11:34:18 浏览次数：2 分类：技术文章

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

题意分析

要求\(k\)种颜色恰好出现\(S\)次

也就是出现\(S\)次的颜色恰好有\(k\)种

我们可以发现\(lim=max\{k\}=min(\frac{n}{s},{m})\)

我们可以容斥一下就是

出现\(S\)次的颜色至少存在\(k\)种

那么

\[dp[k]=C_m^kC_{n}^{ks}(m-k)^{m-ks}\]

应该和好理解的

出现\(S\)次的颜色恰好\(k\)种就是

\[ans[k]=\sum_{j=k}^{lim}(-1)^{j-k}C_j^kdp[j]\]

\(j\)种颜色中\(k\)种被重复算了\(C_j^k\)次

那么我们拆开就是

\[ans[k]* k!=\sum_{j=k}^{lim}\frac{(-1)^{j-k}}{(j-k)!}dp[j]* j!\]

如何求\(\sum_{j=k}^{lim}\frac{(-1)^{j-k}}{(j-k)!}dp[j]* j!\)

我们考虑维护出

\[a[i]=dp[i]* i!\ \ \ \ \ \ b[i]=\frac{(-1)^{i}}{i!}\]

然后就是套路翻转\(a\)序列

那么就是多项式乘法\(NTT\)了

那么对应就是\(lim-j+j-k=lim-k\)

所以我们再反转一下就可以了

然后累加就可以了

CODE:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define ll long long#define inf 0x7fffffff#define N 500008#define IL inline#define M 10000611#define D double#define mod 1004535809#define Gi 334845270 #define R registerusing namespace std;template
                   
                    IL void read(T &_){ T __=0,___=1;char ____=getchar(); while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();} while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();} _=___ ? __:-__;}/*-------------OI使我快乐-------------*/int n,m,s,have,lim,all;ll ans;ll fav[M],fac[M],inv[M],num[M];ll dp[M],cdy[M],wzy[M];int key[M];IL ll C(int x,int y){return fac[x]*fav[x-y]%mod*fav[y]%mod;}IL ll qpow(ll x,ll y){ll res=1;for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;return res;}IL void NTT(ll *A,int knd){ for(R int i=0;i
                    
                     >1]>>1)|((i&1)<<(all-1))); NTT(cdy,1);NTT(wzy,1); for(R int i=0;i

HEOI 2019 RP++

转载于:https://www.cnblogs.com/LovToLZX/p/10590450.html

上一篇：P4562 [JXOI2018]游戏

下一篇：P4313 文理分科

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题意分析

CODE:

HEOI 2019 RP++

发表评论

最新留言

关于作者

推荐文章