题目分析

考虑第一问怎么做，既然需要数最小，按位贪心是经典套路。同时考虑当 $s_n$ 最小的时候，$s_{n-1}$ 最小时一定可以构造出。所以我们不妨枚举每个串尝试让当前串在不小于上一个串的基础上最小，填数存在以下几种情况（优先执行靠前的）：

1. 当这个串某一位规定了值——取这个值，取不了就无解；
2. 如果此时与上一个串前缀不全相同——取 $0$；
3. 否则没有进位：
   1. 如果上一个串这一位是 $1$，那就取 $1$，取不了就无解；
   2. 尝试取 $0$，如果失败了就当上一条处理。

这里判断是否可行可以暴力全部把剩下的位置赋值的尽量大。

考虑第二问，首先 $s_n$ 的限制特殊，考虑把 $s_n$ 赋值为第一问的答案，这样就不用特殊处理了。

我们考虑第一位的 $0,1$ 把序列划分为了两部分，第二位又在之前的基础上每份划分为了两部分，结合数据范围我们发现可以区间 DP。

设 $f_{i,l,r}$ 表示编号 $l\sim r$ 的串在 $i$ 这一位及以后有序的方案数（这里的方案数不考虑 $i$ 这一位之前的方案数）。

转移可以枚举分界点，初始状态是 $f_{m+1,l,r}=1$。

总时间复杂度 $O(nm^2+n^3m)$。

这个时间复杂度看似是错误的，但实际上枚举区间有至少 $\frac{1}{2}$ 的常数（因为 $l\le r$），同时如果还对所有区间的长度和会更少（是 $\sum\limits_{i=1}^{n}i\times(n-i+1)=\frac{n(n+1)(n+2)}{6}$，相当于获得了 $\frac{1}{6}$ 的常数），所以这个时间复杂度是正确的，同时常数小不是卡常而是枚举区间。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=202,p=1e9+7;
int n,m,f[N][N][N];
string s[N],best=" ",lst;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
    }
    for(int i=1;i<=m;i++)
        best+='0';
    for(int i=1;i<=n;i++){
        lst=best;
        for(int j=1,fl=0;j<=m;j++){
            if(!fl){
                if(s[i][j]!='.'){
                    best[j]=s[i][j];
                    if(lst[j]<s[i][j])
                        fl=1;
                    else if(lst[j]==s[i][j]);
                    else{
                        cout<<-1;
                        return 0;
                    }
                }
                else{
                    if(lst[j]=='1')
                        best[j]='1';
                    else{
                        best[j]='0';
                        for(int k=j+1;k<=m;k++){
                            if(s[i][k]!='.')
                                best[k]=s[i][k];
                            else
                                best[k]='1';
                        }
                        if(best<lst)
                            best[j]='1',fl=1;
                    }
                }
            }
            else{
                if(s[i][j]!='.')
                    best[j]=s[i][j];
                else
                    best[j]='0';
            }
        }
    }
    s[n]=best;
    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
            f[m+1][l][r]=1;
    for(int i=m;i>=1;i--){
        for(int l=1;l<=n;l++)
            for(int r=l;r<=n;r++){
                int last0=l-1,first1=r+1;
                for(int j=l;j<=r;j++){
                    if(s[j][i]=='0')
                        last0=max(last0,j);
                    else if(s[j][i]=='1')
                        first1=min(first1,j);
                }
                for(int j=last0;j<first1;j++)
                    (f[i][l][r]+=(l<=j?f[i+1][l][j]:1)*(j+1<=r?f[i+1][j+1][r]:1))%=p;
            }
    }
    cout<<s[n].substr(1,s[n].size()-1)<<' '<<f[1][1][n];
    return 0;
}