abc246F - typewriter

F - typewriter

直接容斥即可，每次选出它们的并集。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=105;
const ll mo=998244353;
const ll inf=1ll<<60;

ll b[N],s[N],l,n,len,ss,tot,z,y,f[N],ans;
char t[N];
ll power(ll a,ll b){
	ll t=1,y=a%mo;
	while (b){
		if (b&1) t=t*y%mo;
		y=y*y%mo;
		b/=2;
	}
	return t;
}
int main()
{
//	freopen("data.in","r",stdin);
	b[0]=1;
	fo(i,1,26) b[i]=b[i-1]*2;
	
	scanf("%lld %lld",&n,&l);
	
	fo(i,1,26) f[i]=power(i,l);
	
	fo(p,0,n-1) {
		scanf("%s",t+1);
		
		len=strlen(t+1);
		fo(i,1,len) {
			s[p]|=b[t[i]-'a'];
		}
	}
	
	fo(st,1,(1<<n)-1) {
		
		tot=0;
		ss=b[26]-1;
		fo(i,0,n-1) if (b[i]&st) ss&=s[i],tot++;
		
		y=0;
		fo(i,0,25) if (ss&b[i]) y++;
		
		if (tot & 1) ans=(ans+f[y])%mo;
		else ans=(ans-f[y])%mo;
	}
	ans=(ans%mo+mo)%mo;
	
	printf("%lld",ans);
	return 0;
}