【实验舱国庆营模拟】Day3 A.code

题目链接

题意：

　　有一个长度为$n$的$01$串$s$，对其进行加密。首先可以得到一个长度为$k$的序列$a_1,a_2, dots ,a_k$。如果$s_1=1$，那么表示$s$由$a_1$个$1$，$a_2$个$0$，$a_3$个$1dots$按顺序拼接而成，否则如果$s_1=0$，那么表示$s$由$a_1$个$0$，$a_2$个$1$，$a_3$个$0dots$按顺序拼接而成。然后，将每个数字表示成二进制数字，按顺序拼接得到字符串$t$，字符串$t$即为对$s$进行加密得到的结果。

　　现在给定一个加密结果$t$，求初始有多少种不同的$s$满足条件。

分析：

　　设$f[i][j]$表示取$t$前$i$位，长度为$j$的$s$计数。

　　直接枚举最后一个分离的数字是$O(n^3)$的。

　　发现某一次分离的数字长度不能超过$log\,n$，转移时取个限制即可。$O(n^2\,log\,n)$。

实现（100分）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define IL inline
#define UI unsigned int
#define RI register int
using namespace std;
typedef long long LL;
const int N=3e3;
const int L=13;
const LL mod=998244353;

    int m,n,t[N+3];
    int l;
    LL f[N+3][N+3];
    
IL int len(int x){
    int ret=0;
    while(x>0){
        ret++;    x>>=1;
    }
    return ret;
}
    
    int s[N+3][L+3];

int main(){
    scanf("%d
",&m);
    char ch;    n=0;
    while(isdigit(ch=getchar()))
        t[++n]=ch-'0';
    
    l=len(n);
    for(int i=n;i>=1;i--){
        s[i][0]=t[i];
        for(int j=1;i-j>0&&j<l;j++)
            s[i][j]=(t[i-j]<<j)+s[i][j-1];
        
    }
    
    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=m;j++)
            for(int k=0;i-k>0&&k<l&&s[i][k]<=j;k++)
            if(t[i-k]==1)
                f[i][j]=(f[i][j]+f[i-k-1][j-s[i][k]])%mod;
    
    LL ans=0;
    for(int i=n;i<=m;i++)
        ans=(ans+f[n][i]);
    printf("%lld",ans*2%mod);

    return 0;

}

小结：

　　DP优化：减少无用转移。