AT_yahoo_procon2019_qual_f 题解

WZY718605 · 2023-12-01 10:42:03 · 题解

思路

先不考虑球的颜色，把一开始第 i 个人手中的两个球都编号为 i 按高桥君收到球的顺序写出一个长为 2N 的数列。

这个数列具有一下性质：

• 第 i 位上的数必须小于等于 i（因为每个球在一次操作中只能向前传递一位）。

且满足以上性质的数列一定是合法的。

再举一个最简单的例子，如果第一个人手里是两个蓝球，显然高桥君第一次不可能收到红球。因此在前 i 次操作完成后，高桥君收到的的红球总数一定小于等于前 i 个人手中红球的总数(i\le n,蓝球同理)。

因此可以用 f_{i,j} 表示前 i+j 次操作中，共收到 i 个红球和 j 个蓝球的方案。若此状态合法则 f_{i,j}\gets f_{i- 1,j}+ f_{i,j- 1}，否则 f_{i,j} \gets 0。

时间复杂度为 O(n^{2})。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
#define il inline
using namespace std ;
const ll mod= 998244353 ;
const int N= 4005 ;
string s ;
int n, sl[N], sr[N] ;
ll f[N][N] ;
int main(){
    cin>> s ; n= s.size() ;
    for (int i= 1; i<= n; i++ ){
        sl[i]= sl[i- 1], sr[i]= sr[i- 1] ;
        if(s[i- 1]== '0') sl[i]+= 2 ;
        else if(s[i- 1]== '1') sl[i]++, sr[i]++ ;
        else sr[i]+= 2 ;
    }
    f[0][0]= 1 ;
    for (int i= 0; i<= sl[n]; i++ ){
        for (int j= 0; j<= sr[n]; j++ ){
            if(i+ j== 0) continue ;
            int k= i+ j ;
            if(k< n&& (i> sl[k]|| j> sr[k])) f[i][j]= 0 ;
            else{
                if(i) f[i][j]+= f[i- 1][j] ; if(j) f[i][j]+= f[i][j- 1] ;
                if(f[i][j]>= mod) f[i][j]-= mod ;
            }
        }
    }

    printf("%lld\n", f[sl[n]][sr[n]]) ;
    return 0 ;
}