CF1679F 题解

eEfiuys · 2024-11-19 21:07:13 · 题解

Difficulty: *2600
Duel 的时候花了 27min47s 把对面秒了。

显然有若干个等价类，所以只需要对等价类计数就好。
每个等价类只取最小的数作为代表，所以就是要求出，有多少个 n 位数，使得它不能通过操作变得更小。

设 ok_{u,v}=\text{true} 表示输入中不存在无序对 (u,v)。
考虑什么时候可以在下一位填一个 k，就是，填上 k 之后，往前一直能换就换，过程中不能碰到一个大于 k 的。
所以当这一位填了 x 之后：

• 所有 ok_{x,k}=\text{true} 的 k 都可以填在下一位（这里面包括 x=k），
• 所有 ok_{x,k}=\text{false} \ \wedge \ k<x 的 k 都不能填在下一位，
• 所有 ok_{x,k}=\text{false} \ \wedge \ k>x 的 k，这一位能填的下一位也可以，这一位不能填的下一位也不行。

立即有 f_{i,sta} 表示，现在填完了从高到低前 i 位，下一位能填的数的集合为 sta，有多少种方案。枚举下一位填的数 k，即得 sta'，转移即可。
令 w=10，时间复杂度 O(n\cdot 2^w \cdot w)。

Code Time！

#include<bits/stdc++.h>
using namespace std;
#define int long long
int inf=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
const int N=50005,M=55;
inline void add(int &a,int b){a=(a+b)%mod;}
int n,m,ans,ed=1023;
bool ok[M][M];
int cur,f[2][1024];
int rst[N],jia[N];
void solve(){
    cin>>n>>m;
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            ok[i][j]=1;
    for(int i=1,u,v;i<=m;i++)cin>>u>>v,ok[v][u]=0,ok[u][v]=0;
    for(int i=0;i<10;i++){
        rst[i]=ed;
        for(int j=0;j<i;j++)
            if(!ok[i][j])rst[i]^=(1<<j);
        for(int j=0;j<10;j++)
            if(ok[i][j])jia[i]|=(1<<j);
    }
    cur=0,f[cur][ed]=1;
    for(int i=1;i<=n;i++){
        cur^=1,memset(f[cur],0,sizeof(f[cur]));
        for(int j=0;j<=ed;j++){
            if(!f[cur^1][j])continue;
            f[cur^1][j]%=mod;
            for(int k=0;k<10;k++){
                if(!((j>>k)&1))continue;
                int jj=(j&rst[k])|jia[k];
                f[cur][jj]+=f[cur^1][j];
            }
        }
    }
    for(int i=0;i<=ed;i++)add(ans,f[cur][i]);
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    int aqx=1;
    while(aqx--)solve();
    return 0;
}