1.CF1194G 另一个MEME问题

#include <bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int INF=105;
const int INFN=15;
const int Mod=998244353;
string s1;
int len;
int res;
struct _node_data{
    int a1,a2,a3,b1,b3;
    // a -> 分子进位为 a1,
    // a2 (0 n>x) (1 n=x) (2 n<x)
    // a3 出现的数码 

    // b -> 分母进位为 b1
    // b3 为出现的数码 
    bool operator < (const _node_data &x) const {
        if (x.a1!=a1) return x.a1<a1;
        else if (x.a2!=a2) return x.a2<a2;
        else if (x.a3!=a3) return x.a3<a3;
        else if (x.b1!=b1) return x.b1<b1;
        else return x.b3<b3;
    }
};
pii num[INF];
void print(_node_data xx) {
    cout<<xx.a1<<" "<<xx.a2<<" "<<xx.a3<<" "<<xx.b1<<" "<<xx.b3<<" endl\n";
}
void solve(int l,int r) {
    vector < map <_node_data,int> >f(103);
    int tot=0;
    for (int p=1;p<=9;p++) 
        if (l*p<=9 && r*p<=9) 
            num[++tot]={l*p,r*p};

    f[0][{0,1,0,0,0}]=1;
    for (int i=0;i<len;i++) {
        for (auto y:f[i]) {
            auto x=y.fi;
//          cout<<x.a1<<" "<<x.a2<<" "<<x.a3<<" "<<x.b1<<" "<<x.b3<<" endl\n"; 
            for (int j=0;j<=9;j++) {
                int a1=(x.a1+j*l)/10,b1=(x.b1+j*r)/10,a2=x.a2,a3=x.a3,b3=x.b3;
                int xx=(x.a1+j*l)%10,yy=(x.b1+j*r)%10;
                if (xx>s1[i+1]-'0') a2=2;
                else if (xx<s1[i+1]-'0') a2=0;

                for (int q=1;q<=tot;q++)
                    if (num[q].fi==xx) a3|=(1<<(q-1));

                for (int q=1;q<=tot;q++)
                    if (num[q].se==yy) b3|=(1<<(q-1));
                f[i+1][{a1,a2,a3,b1,b3}]+=f[i][x];
                f[i+1][{a1,a2,a3,b1,b3}]%=Mod;
            }
        }
    }
    int ans=0;
    for (auto x:f[len]) {
        auto i=x.fi;
        if (i.a1 || i.b1) continue;
        if (i.a2==2) continue;
//      print(i);
//      cout<<f[len][i]<<" yiw?\n";
        for (int j=0;j<tot;j++)
            if ((i.a3>>j)&1 && (i.b3>>j)&1) {
                ans+=f[len][i],ans%=Mod;
                break;
            }
    }
    res+=ans*2%Mod;res%=Mod;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>s1;len=s1.size();s1=" "+s1;
    for (int i=1;i<=len;i++) res=(res*10+s1[i]-'0')%Mod;
    for (int l=1,r=len;l<=r;l++,r--) swap(s1[l],s1[r]);
//  solve(2,1);
    for (int x=1;x<=9;x++) {
        for (int y=1;y<x;y++) {
            if (__gcd(x,y)>1) continue;
            solve(x,y);
        }
    }
    cout<<res<<"\n";
    return 0;
}

S 是一个 Thue-Morse序列。它是一个由以下方式生成的无限长 01 字符串：