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

容斥原理

$$\begin{gathered} f(S)=\sum _{T\subseteq S}g(T) \\ g(S)=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}f(T) \end{gathered}$$

母函数求组合数

题目

#include
   
    using namespace std;typedef long long ll;int num[30];  // 每个字母的数量ll sup[55];ll tmp[55];int main(){
       int T;    cin>>T;    while(T--){
           for(int i=1;i<=26;++i){
               cin>>num[i];            if(num[i]*i>50)num[i]=50/i;        }        memset(tmp,0,sizeof(tmp));        memset(sup,0,sizeof(sup));        sup[0] = 1;        for(int i=1;i<=26;++i){
               for(int j=0;j<=num[i];++j){
                   for(int k=0;j*i+k<=50;++k){
                       tmp[j*i+k] += sup[k];                }            }            for(int j=0;j<=50;++j){
                   sup[j] = tmp[j];                tmp[j] = 0;            }        }        ll ans = 0;        for(int i=1;i<=50;++i)            ans += sup[i];        cout<
    
     <
    
   

转载地址：http://tgkzi.baihongyu.com/