B
题面看着很吓人，但只要读完就发现很好理解，并且根据题意暴力状压DP即可。
原本忘记可以调顺序，发现后纠结了一下，注意到重复选必然更劣故不用管，所以状压转移的时候，直接枚举选哪个就可以了，经过预处理后效率为\(O(n2^{3m}+nm)\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=405,M=20;
void Max(int& x,int y){
if(y>x) x=y;
}
void Min(int& x,int y){
if(y<x) x=y;
}
int n,m,pw[M];
struct node{
int op,tim,mem;
}p[M],tmp[N][M];
void init1(){
int idx[N];
idx['O']=0; idx['W']=1; idx['T']=2; idx['M']=3; idx['R']=4;
for(int i=0;i<M;i++) pw[i]=(1<<i);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c1,c2;
scanf(" %c%c,%d/%d",&c1,&c2,&tmp[i][j].tim,&tmp[i][j].mem);
tmp[i][j].op=idx[(int)c1];
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
node u=tmp[i][j];
Max(p[j].tim,u.tim);
Max(p[j].mem,u.mem);
if(!p[j].op && u.op){
p[j].op=u.op;
break;
}
}
}
//for(int j=1;j<=m;j++) cout<<j<<" "<<p[j].op<<" "<<p[j].tim<<" "<<p[j].mem<<endl;
}
int a[N],b[N],lim[1<<18];
void init2(){
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
node u=tmp[i][j+1],v=p[j+1];
if(u.op && u.op==v.op) a[i]+=pw[j*3];
if(u.tim==v.tim) a[i]+=pw[j*3+1];
if(u.mem==v.mem) a[i]+=pw[j*3+2];
if(u.op && u.op!=v.op) b[i]+=pw[j*3];
if(u.tim>v.tim) b[i]+=pw[j*3+1];
if(u.mem>v.mem) b[i]+=pw[j*3+2];
}
//cout<<i<<" "<<a[i]<<" "<<b[i]<<endl;
}
for(int i=0;i<pw[m*3];i++){
int u=0;
for(int j=0;j<m;j++){
if( !(i&pw[j*3]) ) u+=pw[j*3];
}
lim[i]=u*7;
}
}
int f[1<<18],frt[1<<18],pos[1<<18];
void dp(){
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int j=0;j<pw[m*3];j++){
for(int i=1;i<=n;i++){
if(b[i]&lim[j]) continue;
int u=(j|(a[i]&lim[j]));
if(f[j]+1<f[u]){
f[u]=f[j]+1;
frt[u]=j;
pos[u]=i;
}
}
}
int s=pw[m*3]-1;
for(int j=0;j<m;j++) if(!p[j+1].op) s-=pw[j*3];
//cout<<"s="<<s<<endl;
cout<<f[s]<<endl;
stack<int>q;
while(s){
q.push(pos[s]);
s=frt[s];
}
while(!q.empty()) printf("%d ",q.top()),q.pop();
}
int main()
{
//freopen("1.in","r",stdin);
init1();
init2();
dp();
return 0;
}
D
列出式子后直接往普通幂转下降幂的方向想（因为变成下降幂之后就可以无穷级数求和再求导了），然后搞了半天发现不可做（中间推错了几次，一度以为可做），因为最后变成\(f(k)=\sum_{i=1}^{k} \{k,i \}g(i)\)，用各种第二类斯特林数的公式都难以高效计算出所有的\(f(k)\)。
所以考虑其它方向：
首先发现\(E(n^k)\)中的n拆成两部分后，用二项式展开是EGF的卷积形式，所以求出一张牌的期望F后，\(F^n\)即为n张牌的期望。
列出级数的式子后发现是等比*k次等差，考虑经典错位相减，然后发现F(k)可以化成i<k的F(i)乘组合数，用EGF即可求出F。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+5,P=998244353,G[2]={3,(P+1)/3};
int Mul(int a,int b){
return 1ll*a*b%P;
}
int Add(int a,int b){
a+=b;
if(a>=P) a-=P;
if(a<0) a+=P;
return a;
}
inline int fpw(int a,int x){
int s=1;
for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
return s;
}
int rv[N],gp[2][N],iv[N],fc[N],fv[N];
void init(int n){
fc[0]=1;
for(int i=1;i<n;i++) iv[i]=fpw(i,P-2),fc[i]=1ll*fc[i-1]*i%P;
fv[n-1]=fpw(fc[n-1],P-2);
for(int i=n-2;~i;i--) fv[i]=1ll*fv[i+1]*(i+1)%P;
for(int p=0;p<2;p++){
for(int i=1;i<n;i<<=1){
gp[p][i]=1;
int t=fpw(G[p],(P-1)/(i<<1));
for(int j=i+1;j<(i<<1);j++) gp[p][j]=1ll*gp[p][j-1]*t%P;
}
}
}
void print(char name[],int n,int* a){
printf("%s n=%d\n",name,n);
for(int i=0;i<n;i++) cout<<a[i]<<" "; puts("");
}
inline void dft(int* a,int n,int p){
for(int i=0;i<n;i++) if(i<rv[i]) swap(a[i],a[rv[i]]);
for(int i=1;i<n;i<<=1){
for(int j=0;j<n;j+=(i<<1)){
for(int k=0;k<i;k++){
int &A=a[i+j+k],&B=a[j+k],t=1ll*gp[p][i+k]*A%P;
A=B-t; if(A<0) A+=P;
B=B+t; if(B>=P) B-=P;
}
}
}
if(p) for(int i=0;i<n;i++) a[i]=1ll*a[i]*iv[n]%P;
}
inline int Rev(int m){
int p=0,n=1;
while(n<m) n<<=1,p++;
for(int i=0;i<n;i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(p-1));
return n;
}
inline void poly_mul(int m,int* A,int* B,int* C){
int n=Rev(m);
dft(A,n,0); dft(B,n,0);
for(int i=0;i<n;i++) C[i]=1ll*A[i]*B[i]%P;
dft(C,n,1);
fill(C+m,C+n,0);
}
//C=A*B m:需要C的0~(m-1)项,m~(n-1)为空
int C[N],D[N];
inline void poly_inv(int m,int *a, int *b) {
if(m==1){
b[0]=fpw(a[0],P-2);
return;
}
poly_inv((m + 1)>>1,a,b);
int n=Rev(m<<1);
copy(a,a+m,C);
fill(C+m,C+n,0);
dft(b,n,0); dft(C,n,0);
for(int i=0;i<n;i++) b[i]=1ll*b[i]*(P+2-1ll*b[i]*C[i]%P)%P;
dft(b,n,1);
fill(b+m,b+n,0);
}
//a*b=1,给定a的0~(m-1)项，返回b的0~(m-1)项
//需要保证初始b为空!
inline void poly_Ln(int m,int* a,int* b){
poly_inv(m,a,b);
for(int i=0;i<m-1;i++) C[i]=1ll*a[i+1]*(i+1)%P; C[m-1]=0;
int n=Rev(m<<1);
fill(C+m,C+n,0);
dft(C,n,0); dft(b,n,0);
for(int i=0;i<n;i++) b[i]=1ll*C[i]*b[i]%P;
dft(b,n,1);
for(int i=m-1;i;i--) b[i]=1ll*b[i-1]*iv[i]%P; b[0]=0;
fill(b+m,b+n,0);
}
//b=Ln(a),给定a的0~(m-1)项，返回b的0~(m-1)项
//需要保证初始b为空!
inline void poly_Exp(int m,int* a,int* b){
if(m==1){
b[0]=1;
return;
}
poly_Exp((m+1)>>1,a,b);
poly_Ln(m,b,D);
for(int i=0;i<m;i++) D[i]=(P+a[i]-D[i]+(i==0))%P;
int n=Rev(m<<1);
dft(b,n,0); dft(D,n,0);
for(int i=0;i<n;i++) b[i]=1ll*b[i]*D[i]%P;
dft(b,n,1);
fill(b+m,b+n,0);
fill(D,D+n,0);
}
//b=Exp(a),给定a的0~(m-1)项，返回b的0~(m-1)项
//需要保证初始b为空!
int n,m,a,b,p,q;
int A[N],B[N],E[N],F[N],g[N];
int main(){
cin>>n>>m>>a>>b;
init((n+m)<<2);
p=Mul(a,fpw(b,P-2));
q=Add(P+1,-p);
B[0]=1;
for(int i=0;i<=m;i++) A[i]=fv[i],B[i]=Add(B[i],P-Mul(q,A[i]));
poly_inv(m+1,B,E);
poly_mul(m+m+1,A,E,F);
fill(F+m+1,F+m+m+1,0);
poly_Ln(m+1,F,g);
fill(F,F+m+1,0);
for(int i=0;i<=m;i++) g[i]=Mul(g[i],n);
poly_Exp(m+1,g,F);
for(int i=0;i<=m;i++) printf("%d\n",Mul(F[i],fc[i]));
return 0;
}