employ

ax_by_c · 2025-11-02 07:23:15 · 生活·游记

永久置顶，警钟敲烂

赛时就做了一点点，我做题咋这么慢？

主攻 A 性质 O(n^4)。

先刻画这个结构，不难发现是一段 >0，一个 \le0，一段 >1，一个 \le1 这样的形态。

考虑对 \le x 的那些点（下称关键点）dp，设 f_{i,j} 表示第 i 个位置对应了 \le j 关键点的方案数，但是不好转移。

考虑同时转移相同值，再加一维用来延迟结算：设 f_{i,j,k} 表示第 i 个位置对应了 \le j 关键点且共有 k 个 \le j 已经定好的方案数，转移只需要预处理 cnt 前缀和然后枚举下一个关键点和前面填 j+1 的个数，然后乘一车系数即可 O(n^5)，随便优化一下就是 O(n^4)，后面不是很能想象出来。

赛时写完这部分组合数差了十万八千里，调了一年，然后只有十几分钟了，拼上状压就跑了。

把 A 去掉的话，大概就是初始状态和转移范围改一下，然后 s_i=0 的位置系数改一下，结束状态改一下。

然后观察代码可以发现把排列组合非零也当作限制的话有一维会变成 cnt，和另一维合起来一共是 n，于是是 O(n^3)。

下面给出补的代码。

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l),qwp=(r);i<=qwp;i++)
#define per(i,r,l) for(int i=(r),qwp=(l);i>=qwp;i--)
using namespace std;
namespace ax_by_c{
typedef long long ll;
constexpr ll mod=998244353;
constexpr int N=505;
inline int frint(){int n=0;char c=getchar();while(c<'0'||'9'<c)c=getchar();while('0'<=c&&c<='9')n=n*10+c-48,c=getchar();return n;}
inline int fr01(){char c=getchar();while(c<'0'||'1'<c)c=getchar();return c-'0';}
inline void wrint(int x){if(x>9)wrint(x/10);putchar(x%10+48);}
inline void add(int &x,ll y){x=(x+y)%mod;}
ll ksm(ll a,ll b,ll p){a=a%p;ll r=1;while(b){if(b&1)r=r*a%p;a=a*a%p,b>>=1;}return r%p;}
ll fac[N],inv[N];
void Init(int n){
    fac[0]=1;rep(i,1,n)fac[i]=fac[i-1]*i%mod;
    inv[n]=ksm(fac[n],mod-2,mod);per(i,n,1)inv[i-1]=inv[i]*i%mod;
}
inline ll C(int n,int m){if(n<m||m<0)return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;}
inline ll A(int n,int m){if(n<m||m<0)return 0;return fac[n]*inv[n-m]%mod;}
int n,m,s[N],cnt[N],nxt[N],f[N][N][N],g[N][N];
inline int gc(int l,int r){return (!l)?(cnt[r]):(cnt[r]-cnt[l-1]);}
void main(){
    n=frint(),m=frint();Init(n);
    bool ff=0;
    rep(i,1,n)s[i]=fr01(),ff|=!s[i];rep(i,1,n){int x;x=frint(),cnt[x]++,ff|=!x;}
    if(!ff)return (void)(wrint((int)fac[n]),putchar('\n'));
    rep(i,1,n)cnt[i]+=cnt[i-1];nxt[n]=n;per(i,n-1,1)nxt[i]=((!s[i])?(i):(nxt[i+1]));
    rep(i,1,n){
        add(f[i][0][1],gc(0,0));
        if(!s[i]){add(f[i][0][0],1);break;}
    }
    rep(i,1,n){
        rep(j,0,i-1)rep(k,0,i)add(f[i][j][k],g[j][k]);
        if(!s[i])rep(j,0,i-1)rep(k,0,i)g[j][k]=0;
        rep(j,0,i-1)rep(k,0,i){
            if(!f[i][j][k])continue;
            int w=gc(j+1,j+1);
            rep(q,0,min(w,i-k))add(g[j+1][k+q+1],(ll)f[i][j][k]*(A(w,q+1)*C(i-k,q)%mod+(gc(0,j)-k)*A(w,q)%mod*C(i-k,q)%mod));
            if(!s[nxt[i+1]])rep(q,0,min(w,i-k))add(f[nxt[i+1]][j+1][k+q],(ll)f[i][j][k]*A(w,q)%mod*C(i-k,q));
        }
    }
    int ans=0;
    per(i,n,1){
        rep(j,0,min(n-m-1,i-1))rep(k,0,i)add(ans,(ll)f[i][j][k]*A(gc(j+2,n),n-i)%mod*A(gc(j+1,n)-(n-i),i-k));
        if(!s[i])break;
    }
    wrint(ans),putchar('\n');
}
}
int main(){
    // freopen("employ.in","r",stdin);
    // freopen("employ.out","w",stdout);
    ax_by_c::main();
    return 0;
}
/*
ulimit -s 524288
g++ -std=c++14 -O2 -static employ.cpp -o employ.exe
g++ -std=c++14 -O2 -fsanitize=address,leak,undefined employ.cpp -o employ.exe
./employ.exe
*/

upd：挂鸡蛋。