C++14(g++5.4) 解法, 执行用时: 266ms, 内存消耗: 64476K, 提交时间: 2020-05-20 00:49:23

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=998244353;
const int maxn=1010;
pii dp[maxn][maxn<<1][2][2];
int len;
char s[maxn];
void add(int &x,int y)
{
    x+=y;
    if(x>=mod) x-=mod;
}
pii dfs(int pos,int cnt,int f1,int f2)
{
    if(pos==len) return make_pair(0,cnt==len);
    if(dp[pos][cnt][f1][f2].first!=-1) return dp[pos][cnt][f1][f2];
    pii &res=dp[pos][cnt][f1][f2];
    res=make_pair(0,0);
    int up1=f1?1:s[pos]-'0';
    for(int i=0;i<=up1;++i){
        int up2=f2?1:i;
        for(int j=0;j<=up2;++j){
            int d=cnt+i-j;
            pii tmp=dfs(pos+1,d,f1||i<up1,f2||j<up2);
            add(res.first,tmp.first);
            add(res.first,(ll)tmp.second*abs(d-len)%mod);
            add(res.second,tmp.second);
        }
    }
    return res;
}
int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%s",s);
    len=strlen(s);
    printf("%d\n",dfs(0,len,0,0));
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 111ms, 内存消耗: 70508K, 提交时间: 2020-05-15 22:43:30

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=998244353;
ll ans,n,i,j,k,i1,i2,jj,j2,l,nt,f[1010][2010][2][2],g[1010][2010][2][2];
char s[1010];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	f[0][n][1][1]=1;
	for(i=1;i<=n;i++)
	 for(j=-i;j<=i;j++)
	  for(i1=0;i1<=1;i1++)
	   for(i2=0;i2<=1;i2++)if(f[i-1][j+n][i1][i2]){
	   	for(k=0;k<=1;k++)
	   	 for(l=0;l<=1;l++){
	   	 	if(i1&&k>l)continue;
	   	 	if(i2&&l&&s[i]=='0')continue;
	   	 	jj=i1&&(k==l);j2=i2&&(s[i]-'0'==l);
	   	 	nt=j+(k==0)-(l==0);
	   	 	(f[i][nt+n][jj][j2]+=f[i-1][j+n][i1][i2])%=p;
	   	 	(g[i][nt+n][jj][j2]+=g[i-1][j+n][i1][i2]+f[i-1][j+n][i1][i2]*abs(nt))%=p;
		  }
	   }
	for(i=0;i<=1;i++)
	 for(j=0;j<=1;j++)ans=(ans+g[n][n][i][j])%p;
	printf("%lld",ans);
}