cf1620g Subsequences Galore
给定一个字符串序列 \([t_1,t_2,\cdots ,t_m]\) , 定义 \(f([t_1,t_2,\cdots,t_m])\) 为至少是其中一个字符串 \(t_i\) 的子序列的字符串个数，其中 \(f([])=0\) .
给定哟个字符串序列 \([s_1,s_2,\cdots ,s_m]\) 对每一个子集 \([s_{i_1}, s_{i_2}, \dots, s_{i_k}]\) 求出 \(f({[s_{i_1}, s_{i_2}, \dots, s_{i_k}]})\) 对 \(998,244,353\) 取模后的值。
输出 \(f({[s_{i_1}, s_{i_2}, \dots, s_{i_k}]})\times k\times (i_1+i+2+\cdots+i_k)\) 的异或和（不取模）。
注意每个字符串 \(s_i\) 中的字母都是排好序的。
\(1\leq n\leq 23,1\leq |s_i|\leq 2\cdot 10^4\)
正着求 \(f(S)\) 很难，考虑反着，那就是 容斥 ！
用 \(g(S)\) 表示字符串集合为 \(S\) 时，在 \(S\) 中每一个集合都出现的字符串个数 . 此时的时间复杂度为 \(O(|\sum|n2^n )\)，这个大概在 \(5\cdot 10^9\) 左右，时限是 10s ，可以跑过去 .
对于每个 \(f(S)\) 可以通过枚举子集以 \(O(3^n)\) 的时间复杂度求出，此时这个做法的时间复杂度就是 \(O(\sum n2^n+3^n)\) . 很显然，过不去 .
code
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include
using namespace std;
char in[1000005];
int iiter=0,llen=0;
inline char get(){
if(iiter==llen)llen=fread(in,1,100000,stdin),iiter=0;
if(llen==0)return EOF;
return in[iiter++];
}
inline int rd(){
char ch=get();while(ch<'0'||ch>'9')ch=get();
int res=0;while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=get();
return res;
}
inline void pr(long long res){
if(res==0){putchar('0');return;}
static int out[20];int len=0;
while(res)out[len++]=res%10,res/=10;
for(int i=len-1;i>=0;i--)putchar(out[i]+'0');
}
inline string getstr(){
char ch=get();string res="";
while(isspace(ch))ch=get();
while(!isspace(ch))res+=ch,ch=get();
return res;
}
const int mod=998244353;
int n;
string s[24];
int builtin_popcount[1<<24];
int f[1<<24],g[1<<24];
int cnt[24][30];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=rd();
for(int i=0;i 但是此时，通过仔细思考，可以发现，在复杂度瓶颈 \(O(3^n)\) 的地方 .
for(int msk=0;msk<(1<当 \(|S|\) 是偶数的时候，将 \(g(S)\) 取反，那么 \(f(S)\) 就等于子集相加，可以用高维前缀和做到 . 于是将 \(O(3^n)\) 优化到 \(O(n2^n)\) .
时间复杂度 : \(O(|\sum|n2^n+n2^n)\)
空间复杂度 : \(O(2^n)\)
code
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include
using namespace std;
char in[1000005];
int iiter=0,llen=0;
inline char get(){
if(iiter==llen)llen=fread(in,1,100000,stdin),iiter=0;
if(llen==0)return EOF;
return in[iiter++];
}
inline int rd(){
char ch=get();while(ch<'0'||ch>'9')ch=get();
int res=0;while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=get();
return res;
}
inline void pr(long long res){
if(res==0){putchar('0');return;}
static int out[20];int len=0;
while(res)out[len++]=res%10,res/=10;
for(int i=len-1;i>=0;i--)putchar(out[i]+'0');
}
inline string getstr(){
char ch=get();string res="";
while(isspace(ch))ch=get();
while(!isspace(ch))res+=ch,ch=get();
return res;
}
const int mod=998244353;
int n;
string s[24];
int builtin_popcount[1<<24];
int f[1<<24];
int cnt[24][30];
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=rd();
for(int i=0;i