题解 P4996 【咕咕咕】

· · 题解

显然，由于题目是求所有方案下羞愧值的和，所以对于每个状态，我们只要计算这些状态总共会出现多少次，再将出现次数乘上相应的权值就行了。

对于计算每个状态的出现次数，我们可以将它们看做中间状态，计算从全0变为它们的方案以及从它们到全1的方案，根据乘法原理相乘，就可以得到每个方案的出现次数。

显然具有相同1/0个数的状态，出现次数一样，因为0/1的位置是不重要的，重要的是数量，所以我们只要计算填i个1有多少种方案(1<=i<=n)。

设Opt[i]为填i个1的方案数，我们考虑最后一次一次性填了j个，选这j个有C(i,j)种选法，再乘上之前的。

于是有

预处理递推一下，最后记录答案时对于每个状态给答案加上Opt[0个数]×Opt[1个数]×A

记得取模。。。比赛二十分钟打完标算算组合数没取模。。。60wawa。。。

话说数据能再大点

#include<bits/stdc++.h>
#define Mod 998244353
#define LL long long
using namespace std;
LL Opt[21],C[21][21],Ans;
int n,m;
void Init(){
    C[0][0]=1;
    for(int i=1;i<=20;++i)
        C[i][0]=1;
    for(int i=1;i<=20;++i)
        for(int j=1;j<=20;++j)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
    Opt[0]=1;
    for(int i=1;i<=20;++i)
        for(int j=1;j<=i;++j)
            Opt[i]=(Opt[i]+Opt[i-j]*C[i][j])%Mod;
}
void Doit(){
    char c;
    int Flag;
    LL Count,A;
    scanf("%d%d",&n,&m);
    while(m--){
        Count=0;
        Flag=0;
        while(Flag<n){
            while((c=getchar())<'0'||c>'1');
            if(c=='1')
                ++Count;
            ++Flag;
        }
        scanf("%lld",&A);
        Ans=(Ans+A*Opt[Count]%Mod*Opt[n-Count]%Mod)%Mod;
    }
    printf("%lld\n",Ans);
}
int main(){
    Init();
    Doit();
    return 0;
}