题目描述

给定正整数 $K$。请构造两个 $01$ 串 $S,T$，使得它们有恰好 $K$ 个本质不同的最长公共子序列。

我们额外给定参数 $L$，只有你构造的串满足 $\max(\vert S\vert ,\vert T\vert)\le L$ 时才能得分。

输入格式

第一行两个正整数 $K,L$。

输出格式

输出两行，分别表示 $S,T$。

样例 1

1 10000

1
0

样例 2

2 10000

10
01

样例 3

3 10000

101
0110

样例 4

4 10000

1001
0110

每个样例输出的 LCS：

1: (空串)

2: 0 , 1

3: 01 , 10 , 11

4: 00 , 01 , 10 , 11

限制

Subtask #1 (10 分)：$L=10^4,K<\frac{L}{2}$。

Subtask #2 (15 分)：$L=10^4,K\le 10^9,K=\binom{k}{3}$。

Subtask #3 (20 分)：$L=10^4,K\le 10^6$。

Subtask #4 (20 分)：$L=10^4,K\le 10^9$。

Subtask #5 (15 分)：$K=2^k$。

Subtask #6 (20 分)：无特殊限制。

对于所有数据，$K\le 10^{15},L\ge 10^3$。

检查

运行下面的代码，输入 $S,T$。设本质不同 LCS 个数为 $C$，它会输出 $\min(10^{15}+1,C)$。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a),_=int(b);i<=_;++i)
#define per(i,a,b) for(int i=int(a),_=int(b);i>=_;--i)
using namespace std;
typedef long long ll;
const ll inf=ll(1e15)+1;
struct node
{
    int len;
    ll cnt;
    node(int len=0,ll cnt=1):len(len),cnt(cnt){}
    node F(){return node{len+1,cnt};}
    node operator+(node o)
    {
        if(len==o.len)return node{len,min(inf,cnt+o.cnt)};
        return len>o.len?*this:o;
    }
};
const int N=1e4+10;
int n,m,a[N][2],b[N][2];
char s[N],t[N];
node dp[3][N];
void init(char *s,int a[N][2],int &n)
{
    n=strlen(s+1);
    rep(i,1,n)
    {
        rep(j,0,1)a[i][j]=a[i-1][j];
        a[i][s[i]-'0']=i;
    }
}
int main()
{
    scanf("%s%s",s+1,t+1);
    init(s,a,n);
    init(t,b,m);
    rep(i,1,n)
    {
        rep(j,0,m)dp[s[i]-'0'][j]=dp[2][j],dp[2][j]=node();
        rep(k,0,1)if(a[i][k])
        rep(j,1,m)if(b[j][k])
        dp[2][j]=dp[2][j]+dp[k][b[j][k]-1].F();
    }
    cout<<"cnt="<<dp[2][m].cnt<<",len="<<dp[2][m].len<<endl;
    return 0; 
}