涉及知识点：数位DP

前言

其实这题也没啥好写的，就是好久没做大模拟调代码把人调废了，警醒一下自己……

题意

大模拟，不给简化题意了

\(n\leq 10^5\)。

思路

大递推 DP 里面套小数位 DP，挺恶心的。

设 \(f_i\) 为以第 \(i\) 字节结尾的方案数，每次考虑用 \(4\) 个字节存并且是以 \(i\) 结尾的数，然后 \(3\) 个字节、\(2\) 个字节……判断合法然后转移即可。

代码

用了个 class 来维护，比复制粘贴四次记搜好看多了。

#include<bits/stdc++.h>
#define add(a,b) a=((a)+(b))%P
#define checkch(x,c) (s[id][x]==c || s[id][x]=='?')
using namespace std;
typedef long long LL;
const LL P=1e9+7;
const int MAXN=1e5+5,FOLLOW=1,HEAD1=2,HEAD2=4,HEAD3=8,HEAD4=16;
int n,type[MAXN];
string s[MAXN];
LL ans=0,f[MAXN];
inline int checktype(const int& id){
    int res=0;
    if(checkch(0,'1') && checkch(1,'0')) res|=FOLLOW;
    if(checkch(0,'0')) res|=HEAD1;
    if(checkch(0,'1') && checkch(1,'1') && checkch(2,'0')) res|=HEAD2;
    if(checkch(0,'1') && checkch(1,'1') && checkch(2,'1') && checkch(3,'0')) res|=HEAD3;
    if(checkch(0,'1') && checkch(1,'1') && checkch(2,'1') && checkch(3,'1') && checkch(4,'0')) res|=HEAD4;
    if(!res){
        // cout<<s[id]<<endl;
        cout<<0<<endl;
        exit(0);
    }
    return res;
}
class DigitDP{
    private:
        int len;
        LL g[20][2][2];
        string str,lstr,rstr;
    public:
        DigitDP(int _len,string _lstr,string _rstr){
            len=_len;
            lstr=_lstr;
            rstr=_rstr;
        }
        inline void reset(string _str){
            memset(g,-1,sizeof(g));
            str=_str;
        }
        LL dfs(int dep=0,bool liml=true,bool limr=true){
            if(g[dep][liml][limr]!=-1) return g[dep][liml][limr];
            if(dep>=len){
                return g[dep][liml][limr]=1;
            }
            LL res=0;
            if(str[dep]=='?'){
                for(int dig=(liml?(lstr[dep]-'0'):0);dig<=(limr?(rstr[dep]-'0'):1);dig++){
                    add(res,dfs(dep+1,liml&&(dig==lstr[dep]-'0'),limr&&(dig==rstr[dep]-'0')));
                }
            }
            else if(str[dep]=='1'){
                if((!limr) || (rstr[dep]=='1'))
                    add(res,dfs(dep+1,liml&&('1'==lstr[dep]),limr&&('1'==rstr[dep])));
            }
            else{
                if((!liml) || (lstr[dep]=='0'))
                    add(res,dfs(dep+1,liml&&('0'==lstr[dep]),limr&&('0'==rstr[dep])));
            }
            return g[dep][liml][limr]=res;
        }
}
dp8 (8, "00000001","11111111"),
dp11(11,"00010000000","11111111111"),
dp16(16,"0000100000000000","1111111111111111"),
dp18(18,"010000000000000000","110001001101001111");
int main(){
    // freopen("utf.in","r",stdin);
    // freopen("utf.out","w",stdout);

    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        type[i]=checktype(i);
        // cout<<i<<' ';
        // if(type[i]&FOLLOW) cout<<"FOLLOW"<<' ';
        // if(type[i]&HEAD1) cout<<"HEAD1"<<' ';
        // if(type[i]&HEAD2) cout<<"HEAD2"<<' ';
        // if(type[i]&HEAD3) cout<<"HEAD3"<<' ';
        // if(type[i]&HEAD4) cout<<"HEAD4"<<' ';
        // cout<<endl;
    }
    f[0]=1;
    for(int i=1;i<=n;i++){
        if(i>=1 && (type[i]&HEAD1)){
            string tmp;
            for(int j=1;j<=7;j++) tmp+=s[i][j];
            dp8.reset(tmp);
            add(f[i],f[i-1]*dp8.dfs()%P);
        }
        if(i>=2 && (type[i-1]&HEAD2) && (type[i]&FOLLOW)){
            string tmp;
            for(int j=3;j<=7;j++) tmp+=s[i-1][j];
            for(int j=2;j<=7;j++) tmp+=s[i][j];
            dp11.reset(tmp);
            add(f[i],f[i-2]*dp11.dfs()%P);
        }
        if(i>=3 && (type[i-2]&HEAD3) && (type[i-1]&FOLLOW) && (type[i]&FOLLOW)){
            string tmp;
            for(int j=4;j<=7;j++) tmp+=s[i-2][j];
            for(int j=2;j<=7;j++) tmp+=s[i-1][j];
            for(int j=2;j<=7;j++) tmp+=s[i][j];
            dp16.reset(tmp);
            add(f[i],f[i-3]*dp16.dfs()%P);
        }
        if(i>=4 && (type[i-3]&HEAD4) && (type[i-2]&FOLLOW) && (type[i-1]&FOLLOW) && (type[i]&FOLLOW)){
            bool flag=1;
            for(int j=5;j<=7 && flag;j++)// 四个字节的情况虽然只有后18位有效，但是还是需要判断第一个字节的后三位是否为0
                if(s[i-3][j]=='1') flag=0;
            if(flag){
                string tmp;
                for(int j=2;j<=7;j++) tmp+=s[i-2][j];
                for(int j=2;j<=7;j++) tmp+=s[i-1][j];
                for(int j=2;j<=7;j++) tmp+=s[i][j];
                dp18.reset(tmp);
                add(f[i],f[i-4]*dp18.dfs()%P);
            }
        }
    }
    cout<<f[n]<<endl;
    return 0;
}