2026 牛客寒假集训营-5

1. B-智乃的瓷砖

题目描述

智乃想要在他家的浴室密铺一种菱形图案的瓷砖，具体来讲，她现在有两种不同图案的瓷砖，一种是 "/"（斜杠）形状，另一种是 "\"（反斜杠）形状的。
假设她家的墙面可以看做是一个 行 列的二维字符矩阵，现在规定其左上角的形状为 "/" 型，且每一对上下相邻、左右相邻的瓷砖均形状不同。

例如，下面这个字符矩阵就是一个 的图形：

/\/\/\/\/\
\/\/\/\/\/

请你告诉智乃这面墙在铺好瓷砖后的形状应该是怎样的。

输入描述

在一行上输入两个正整数 ，表示智乃家墙面的行数、列数。

输出描述

请输出一个 行 列的字符矩阵，表示墙面的形状。

解题思路

注意一下反斜杠前面需要转义

AC 代码

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i&1){
                if(j&1)cout<<'/';
                else cout<<'\\';
            }
            else{
                if(j&1)cout<<'\\';
                else cout<<'/';     
            }
        }
        cout<<"\n";
    }
}

2. J-智乃的幻方

题目描述

如果一个 行 列的矩阵的行、列、两条对角线上的数字之和相同，且 个位置上的数字为 出现各一次，则称这个 行 列的矩阵为一个三阶幻方。

现在智乃有一个 行 列的矩阵，请你告诉她这个矩阵是否满足幻方的条件，如果满足输出 ，否则输出 。

输入描述

一共三行，第 行输入三个正整数 ，表示矩阵第 行的数字。

输出描述

如果矩阵满足条件，输出 ；否则输出 。

解题思路

先判断1-9每一个数字都必须出现一次，再判断行和列，最后判断对角线

AC 代码

void solve(){
    for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++){
            cin>>a[i][j];
            res[a[i][j]]++;
        }
    }
    for(int i=1;i<=9;i++){
        if(res[i]!=1){
            cout<<"No\n";
            return ;
        }
    }
    int res=a[0][0]+a[0][1]+a[0][2];
    for(int i=0;i<=2;i++){
        int temp=0;
        for(int j=0;j<=2;j++){
            temp+=a[i][j];
        }
        if(temp!=res){
            cout<<"No\n";
            return ;
        }
        temp=0;
        for(int j=0;j<=2;j++){
            temp+=a[j][i];
        }
        if(temp!=res){
            cout<<"No\n";
            return ;
        }
    }
    int temp=a[0][0]+a[1][1]+a[2][2];
    if(temp!=res){
        cout<<"No\n";
        return ;
    }
    temp=a[2][0]+a[1][1]+a[0][2];
    if(temp!=res){
        cout<<"No\n";
        return ;
    }
    cout<<"Yes\n";
    return ;
}

3. G-智乃的箭头魔术

题目描述 本题为直接提交答案类型题目，后台仅有一组测试数据且与题目中给出的输入完全相同，您可以在本地通过各种方式>得出答案，建议在提交语言中选择PHP直接提交答案的内容而不必编写一个输出答案的程序。

智乃有一张长度为 单位、宽度为 单位的纸，在上面画了两个箭头，如下图所示：

智乃现在将这张纸沿虚线将右侧图形对折到左边，并且用胶水将这两个箭头黏在一起，并且在整个过程中保持左侧图形不动，使其成为一个正反两面的正方形折纸玩具，如下图所示：

假设该折纸玩具的初始状态为箭头指向右上方向（注意无论正反哪一面都是等价的），定义 种操作从 到 >，操作数的定义如下：
操作 ，表示该折纸玩具按照中垂线（垂直对称轴）翻转（如图所示 '|' 形的竖线）；
操作 ，表示该折纸玩具按照主对角线翻转（如图所示 '/' 形的对角线）；
操作 ，表示该折纸玩具按照水平线翻转（如图所示 '-' 形的横线）；
操作 ，表示该折纸玩具按照副对角线翻转（如图所示 '\' 形的对角线）；
操作 ，表示该折纸玩具顺时针旋转 度；
操作 ，表示该折纸玩具逆时针旋转 度。
所有翻转轴与旋转方向均相对于观察者的固定空间参考系，不随纸张的变换而改变。

接下来，智乃将进行 次操作，每次操作完成后，智乃都会询问你当前箭头的状态，状态即在某次操作后，箭头的朝向，如下图所示：
代表右上；
代表右下；
代表左下；
代表左上。

>

例如，假设智乃的操作序列是：

012345

那么你应该回答：

310232

现在具体的 次真实操作序列如下：

0112233445142015320125410214530214510214102302142025101203201451451522302514203214510021454101002532

你需要输出一个长度为 的字符串，第 位表示执行完前 次操作后箭头的状态。

输入描述

本题不需要处理输入，判题时也不会提供任何程序输入。

输出描述

在一行上输出一个长度为 、仅包含数字 的字符串，表示智乃每次操作完成后箭头的状态。

建议在提交语言中选择PHP直接提交答案的内容而不必编写一个输出答案的程序。

解题思路

情况不多的小模拟，直接写就行

AC 代码

void solve(){
    int pre=0;
    int n=100;
    string res="0112233445142015320125410214530214510214102302142025101203201451451522302514203214510021454101002532";
    for(int i=0;i<res.size();i++){
        int temp=res[i]-'0';
        if(temp==0){
            pre=3-pre;
        }
        else if(temp==1){
            if(pre==1||pre==3){
                pre=4-pre;
            }
        }
        else if(temp==2){
            if(pre<=1)pre=1-pre;
            else pre=5-pre;
        }
        else if(temp==3){
            if(pre==0||pre==2)pre=2-pre;
        }
        else if(temp==4){
            pre=pre+1;
            pre=pre%4;
        }
        else if(temp==5){
            pre=pre-1;
            pre=(pre+4)%4;
        }
        cout<<pre;
    }
    cout<<"\n";
}

4. D-智乃的果子

题目描述 智乃有 种不同的果子，第 种果子有 个，重量为 。初始时共有 > 堆，每堆只包含 个果子，其重量等于该果子的重量。

智乃可以使用一个操作将任意两堆果子合并成一堆，合并的代价与合并后新堆的重量均为两堆的重量之和。
显然，假设有 堆果子，则进行 次合并操作后，所有果子都会被合并成同一堆。
智乃想知道她把这些果子合并成一堆的最小代价之和是多少。由于答案可能很大，请将答案对 取模后输出。

输入描述

第一行输入一个正整数 ，表示果子的种类数。
此后 行，第 行输入两个正整数 ，表示第 种果子的个数和重量。

输出描述

仅一行一个正整数，表示将所有果子合并成一堆的最小代价之和，对 取模后的结果。

解题思路

数据小的时候用的是区间DP，本题果子太多了，使得最后的代价最小，要每一次都选择最小的两个果子合并，暴力的话是1e11的，通过从小到大枚举1e5种果子，每种果子是偶数的话，直接减半加倍添加在后面，奇数的话，留一个和下一种果子合并一次即可。
使用map和priority_queue都可以

AC 代码

void solve(){
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        mp[b]+=a;
    }
    while(!mp.empty()){
    	auto it=mp.begin();
        int val=it->first;
        int num=it->second;
        mp.erase(it);
        int even=num/2;
        if(even>0){
            ans=(ans+1ll*even*(val*2)%mod)%mod;
            mp[val*2]+=even;
        }
        if(num%2==1&&!mp.empty()){
            auto itt=mp.begin();
            int vall=itt->first;
            int numm=itt->second;
            mp.erase(itt);
            ans=(ans+val+vall)%mod;
            mp[val+vall]++;
            if(numm>1)mp[vall]+=numm-1;
        }
    }
    cout<<(ans+mod)%mod<<"\n";
}

5. F-智乃的算法竞赛群友

题目描述

智乃加了一个算法竞赛群，她发现里面的群友个个都是人才，说话又好听。
她发现每次管理员 qcjj 在发比赛链接时，群友都会往下复读什么 qcjjkkt（清楚姐姐看看题）和 td（题单）。

现在你想要在群里发言，具体来讲，你希望使用 个字符组成一句话。
这句话可以视为是一个长度为 的字符串，其每包含一个 子串，你获得 的快乐值，每包含一个 子串，获得 的快乐值。问能够在群中通过这次发言得到的最大快乐值是多少。
注意子串可以包含公共部分，例如 可以同时包含 和 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

在一行上输入三个正整数 ，表示这句话的长度、包含 子串可以获得的快乐值、包含 子串可以获得的快乐值。

输出描述

对于每组测试数据，新起一行输出一个整数，表示能够通过这次发言得到的最大快乐值。

解题思路

一共有三种方案，花8个长度得到（a+b）个快乐值，花7个长度得到 a 个快乐值，花2个长度得到 b 个快乐值
由于 n 是1e9，无法使用背包完全转移，可以注意到，使用贪心只使用单位价值最大的方案的话，可能会产生冗余的位置无法被填充，所以我们可以提前留一些余量，暴力去枚举，找到余量填充的最优方案

PS

余量开到500就TLE了，留成100以内就能过

AC 代码

void solve(){
    cin>>n>>a>>b;
    int res1=(a+b)*7, res2=a*8, res3=b*28;
    vector<array<int,3>>v;
    v.push_back({res1, a+b, 8});
    v.push_back({res2, a, 7});
    v.push_back({res3, b, 2});
    sort(v.begin(), v.end(), greater<>());
    int ans=0, lim=0, f, res=0;
    if(n>=500) lim=50;
    else {
        lim=n;
        goto part;
    }
    f = n - lim;
    ans += (f / v[0][2])*v[0][1];
    lim += (f % v[0][2]);
part:
    res = 0;
    for(int i=0; i * v[0][2] <= lim; i++){
        for(int j=0; j * v[1][2] + i * v[0][2] <= lim; j++){
            int k = lim - j * v[1][2] - i * v[0][2];
            int knum = k / v[2][2];
            res = max(res, i * v[0][1] + j * v[1][1] + knum * v[2][1]);
        }
    }
    cout << ans + res << "\n";
}

6. E-智乃的最大子段和取模

题目描述

对于一个长度为 的数组 ，给定 ，定义 为数组 的子段和。如果 是使 在所有 的取值中达到了最大值，则称 是最大子段和。

现在给定一个常数 ，智乃想要知道，如果在求得最大子段和的过程中对 取模，那么取模后数组整体的最大子段和应该是多少？
形式化的：记 ，请找到一对 使得 成为最大值，输出 、、这个最大值。如果有多种可行的答案，你可以输出任意符合条件的 。

请注意：本题需要输出在计算过程中取模后的子段和的最大值，而不是传统意义上的最大子段和对答案取模。

【名词解释】
 ：代表取模运算。例如， 除以 的余数为 ，因此式子 的值为 。

输入描述

第一行输入两个正整数 ，表示数组的长度、模数。
第二行输入 个非负整数 ，表示数组中的元素。

输出描述

在一行中输出三个整数，分别表示 、、取模后的最大子段和。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

解题思路

存一下前缀和以及每种前缀和第一次出现的下标，O(1)查询子段和结果和两个端点。
查找取模后的最大子段和，
要么sumr >= suml , 则结果不需要取模，在 r 这个右端点上取最小的suml
要么sumr < suml , 则结果需要取模，在 r 这个右端点上取比sumr大的最小的suml 使得取模后结果接近模数
使用set二分查询就行

PS

简单二分

AC 代码

void solve(){
    cin>>n>>p;
    a.assign(n+1,0);
    sum.assign(n+1,0);
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans=-1,ansl=1,ansr=1;
    for(int i=1;i<=n;i++){
        if(a[i]%p>ans){
            ans=a[i]%p;
            ansl=i;
            ansr=i;
        }
    }
    for(int i=1;i<=n;i++){
        sum[i]=(sum[i-1]+a[i])%p;
    }
    set<int>uns;
    uns.insert(0);
    mp[0]=0;
    for(int i=1;i<=n;i++){
        int val=sum[i];
        auto it=uns.begin();
        int minn=*it;
        int res=(val-minn+p)%p;
        if(res>ans){
            ans=res;
            ansl=mp[minn]+1;
            ansr=i;
        }
        it=uns.upper_bound(val);
        if(it!=uns.end()){
            int minn=*it;
            int res=(val-minn+p)%p;
            if(res>ans){
                ans=res;
                ansl=mp[minn]+1;
                ansr=i;
            }
        }
        if(!mp.count(val)){
            uns.insert(val);
            mp[val]=i;
        }
    }
    cout<<ansl-1<<" "<<ansr-1<<" "<<ans<<"\n";
}

7. I-智乃挖坑

题目描述

泰拉瑞亚是一款2D沙盒游戏，在游戏中玩家可以在游戏中做很多事情：制造武器战胜各种各样的敌人及群落；挖掘地下寻找器材配件、金钱和其他有用的东西；收集木材，石材，矿石等资源；用世界里的一切创造你需要的东西并守护它。

在游戏中，玩家一开始位于水平地面，地面可以视为是一个一维数轴，且最左边的坐标是 ，最右侧的坐标是 。初始时，地面所有位置的深度均为 0。智乃想通过 次连续操作在游戏中向下挖一个大坑，具体来讲，在第 次操作中会输入一个坐标 以及向下的力度 ，然后，对于所有整数坐标 ，深度增加 。

例如上图是一次操作 、 时的示意图。

连续操作时会使得每个位置上的影响叠加求和。
假设现在游戏向下的地图边界深度为 ，一旦玩家向下挖坑的过程中，某个位置的深度大于 ，就会挖出地图边界。
现在智乃想知道她在 次向下挖坑的过程中是否存在挖出地图边界的情况，如果存在，则告诉智乃她最早在第几次操作时挖出了地图边界。

输入描述

第一行输入三个正整数 ，表示水平地面的长度、操作次数、挖坑的深度限制。
此后 行，第 行输入两个正整数 ，表示第 次操作的参数。

输出描述

如果智乃不会挖出地图的边界，直接输出 ；否则，第一行输出 ，第二行输出一个整数，表示她是在第几次操作的时候挖出的地图边界。

解题思路

使用优先队列模拟扫描线，两侧的影响分开计算，从两边各扫一遍数组，算出整个数组的深度，进行二分查找最小的答案。

PS

因为我不会二阶差分，所以只能用上面的思路

AC 代码

bool check(int mid){
    vector<int>res(n+2,0); 
    int temp=0;
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i=1;i<=n;i++){
        if(q.size())temp-=q.size();
        while(q.size()&&q.top()<i) q.pop();
        res[i]+=temp;
        for(auto [f,k]:V[i]){
            if(k>mid)break;
            temp+=f;          
            res[i]+=f;       
            q.push(i+f-1);  
        }
    }
    temp=0;
    priority_queue<int> qq;
    for(int i=n;i>=1;i--){
        if(qq.size())temp-=qq.size();
        while(qq.size()&&qq.top()>i)qq.pop();
        res[i]+=temp;
        for(auto [f,k]:V[i]){
            if(k>mid)break;
            temp+=f;          
            qq.push(i-f+1); 
        }
        if(res[i]>h)return true;
    }
    return false;
}

8. H-智乃的矩阵

题目描述

智乃有一个 行 列的正方形矩阵，矩阵的每一个元素都是一个整数，即可以看成是一个长和宽分别为 行 列的二维数组。
智乃现在有一个操作：选择一个 行 列的连续子矩阵，然后选择该子矩阵中两对互不重叠的相邻数字（即两对水平相邻数字，或两对垂直相邻数字），令其中一对的两个数字均增加 ，另一对的两个数字均减少 。
智乃可以无限次的使用（也可以不使用）这个操作，她现在想令整个矩阵中所有的数字都变成相同的值，问她是否可以达成要求。

输入描述

第一行输入一个正整数 ，表示矩阵的大小。
此后 行，第 行输入 个整数 ，表示矩阵第 行的数字。

输出描述

如果可以达到要求，则输出 ；否则输出 。

解题思路

首先，最终状态要求全矩阵数值相等，因此矩阵总和必须能被单元格总数 整除，从而确定目标平均值 avg。
利用国际象棋黑白染色模型，由于每次操作是对相邻的一对格子（即一黑一白）做等量的加减，导致所有黑格的总和与所有白格的总和相对于彼此的差值是恒定不变的。因此，程序必须检查初始状态下黑、白格子的总和是否分别等于目标总和
在数值条件满足后，问题转化为如何消除位置上的差异。将元素值模 2 处理后，原操作等价于“翻转 区域的奇偶性”（即 XOR 1）。此时采用二维扫雷式的贪心策略，从左上角开始遍历，若当前格子不满足奇偶性要求，就强制翻转以它为左上角的 区域。如果遍历结束后所有格子都能归零，则说明可以通过操作达成目标。

PS

扩欧也忘得有点干净了，使用format输出int128 很好用

AC 代码

void solve(){
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            sum+=a[i][j];
        }
    }
    if(n==1){
        cout<<"Yes\n";return ;
    }
    if(sum%(n*n)!=0){
    	cout<<"No\n";
    	return ;
    }
    int avg=sum/(n*n);
    int color[2]={0,0};
    int cnt[2]={0,0};
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
    		int idx=(i+j)&1;
    		color[idx]+=a[i][j];
    		cnt[idx]++;
    	}
    }
    for(int i=0;i<=1;i++){
    	if(color[i]%cnt[i]!=0){
    		cout<<"No\n";
    		return ;
    	}
    	if(color[i]/cnt[i]!=avg){
    		cout<<"No\n";
    		return ;
    	}
    }
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
    		a[i][j]=((a[i][j]-avg)%2+2)%2;
    	}
    }
    for(int i=1;i<n;i++){
    	for(int j=1;j<n;j++){
    		if(a[i][j]==1){
    			a[i][j]^=1;
    			a[i+1][j]^=1;
    			a[i][j+1]^=1;
    			a[i+1][j+1]^=1;
    		}
    	}
    }
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
    		if(a[i][j]){
    			cout<<"No\n";
    			return ;
    		}
    	}
    }
    cout<<"Yes\n";
    return; 
}

9. C-智乃的草坪

题目描述

智乃有一块矩形草坪，从地图正上方俯视，草坪的四个端点分别位于坐标 、、、。
现在智乃有 个自动洒水装置，第 个洒水装置位于坐标 上，浇水速率为 ，保证洒水装置的坐标一定位于草坪内部或边缘。
当这些洒水装置启动， 个时间单位以后，第 个洒水装置洒水的范围是一个以坐标 为圆心，以 为半径的圆。
当经过 个时间单位以后，所有洒水装置洒水的范围覆盖了整个草坪的矩形，就说明智乃完成了她的浇水工作。更具体地，若矩形区域内的所有点 满足 且 均被至少一个启动的圆覆盖，则称完成了浇水工作。

现在由于电力紧缺，智乃发现他至多只能启动其中的 个洒水装置。问智乃完成整个草坪洒水工作的最短时间是多少。显然，在经历足够长的时间后，即使只使用 个洒水器也能完成工作，所以答案一定存在。

输入描述

第一行输入四个非负整数 ，分别表示总共的洒水装置数、最多启动的洒水装置数、草坪的一半高度和宽度。
此后 行，第 行输入两个整数 ，表示第 个洒水装置的坐标和洒水速率。

输出描述

输出一个实数，表示最短工作时间。

由于实数的计算存在误差，当误差的量级不超过 时，您的答案都将被接受。具体来说，设您的答案为 ，标准答案为 ，当且仅当 时，您的答案将被接受。

解题思路

二分最短工作时间，每一次check中，先判断当前洒水装置能否满足R的限制，然后计算出矩形和圆相截的长度作为当前洒水装置的左右边界，将问题转化为了区间合并的问题，能全部覆盖且不超过K个就符合要求。

AC 代码

bool check(ld mid){
    vector<array<ld,2>>s;
    for(auto &[p,v]:v){
        auto dx=get(v*mid);
        if(dx<0)continue;
        s.push_back({p-dx,p+dx});
    }
    sort(s.begin(),s.end());
    ld l=0,r=0;
    int cnt=0;
    for(auto &[x,y]:s){
        if(x<=l+eps)r=max(r,y);
        else{
            if(r<x-eps)return false;
            l=r;
            r=max(r,y);
            cnt++;
        }
    }
    if(l<C-eps)cnt++;
    if(r<C-eps)return false;
    if(cnt<=k)return true;
    return false;
}

10. A-智乃的二进制

题目描述

智乃定义一个十进制正整数是“好”的，当且仅当其十进制表示中仅包含数字 和 ，且数字 的出现次数不超过 。其十进制表示对应的字符串是其二进制表示对应的字符串的一个后缀。
例如：（10进制），其中只有 个数位为 ，转写成二进制为 （2进制），其二进制包含后缀 ，就说它是“好”的。
前 个“好”数分别为：、、、、、、、、。

现在智乃想要知道，从小到大排列后的第 个符合条件的“好”数是多少。由于答案可能很大，请将答案对 取模后输出。

【名词解释】
字符串的后缀：从字符串的最后一个字符开始，向前连续取若干个字符得到的字符串。更具体地，字符串 后 个字符构成的字符串被称为 的第 个后缀，也记为 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

输入一个正整数 ，表示要查询的第 个“好”数。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示答案对 取模后的结果。

解题思路

由题目可知，好数分为两种 ，一种是 10 ^ A , 一种是 10 ^ A + 10 ^ B 。
第一种全是好数，
而第二种好数A和B存在限制：

• ()** 十进制字符串形如 1 + (a-b-1个0) + 1 + (b个0)。 这要求 的二进制末尾必须匹配这个模式。 首先，末尾要有 个0。因为 ，显然被 整除。 除去末尾 个0，剩下的数是 。 我们需要这个剩余的数，在二进制下，最低位是1，中间 位是0，第 位是1。 数学上这等价于： 推导简化后（利用 为奇数），核心约束变为：

  令 表示 二进制末尾0的个数（即 __builtin_ctzll），由 LTE引理 可推导： (当 )。

  于是限制条件转化为：

  特例 ： 恒成立，所以当 时，所有 都合法。 对于 ，合法的 必须满足 。即 和 的距离不能太远。

然后我们对好数进行按层计数，计算主要的次幂A 层内好数的总数 ：
这个过程分为10^A, 10^A+1,10^A+10^B 的三部分总和，前两个部分的和为（A+1）+A
第三部分对于每个 ，它能贡献的 的个数是 。
在b和A差距比较大的时候，默认为，也就是需要计算 ，利用 Legendre 公式的一个变体：。所以 。
在b和A差距比较小（不超过70）的时候，直接使用公式暴力计算即可。

最后计算目标层的偏移量：

如果在当前层排名第1，答案是 。 否则，我们需要在合法的 集合中找 偏移量 的 。 合法的 包括 ，以及满足 的 。 由于限制极强，满足条件的 必定在 范围内。 直接使用公式 暴力检查这个范围内的 即可找到答案。

PS

难难难

AC 代码

int sum(int n){
	if(n<=0)return 0;
	return 2*n-__builtin_popcountll(n);
}
int cal(int A){
	if(A<0)return 0;
	if(A==0)return 1;
	int total=2*A+1;
	int fg=max(0ll,A-70);
	if(fg>0)total+=sum(fg);
	for(int b=fg+1;b<A;b++){
		total+=min(A-b,(int)__builtin_ctzll(b)+1);
	}
	return total;
}
void solve(){
	int k;cin>>k;
	int l=0,r=2e18,A=0;
	while(l<=r){
		int mid=l+(r-l)/2;
		if(cal(mid)>=k){
			A=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	int num=cal(A-1);
	int res=k-num;
	if(res==1){
		cout<<qmi(10ll,A)<<"\n";
		return ;
	}
	vector<int>ans;
	ans.push_back(0);
	int check=max(1LL,A-70);
	for(int b=check;b<A;b++){
		if(A-b<=__builtin_ctzll(b)+1){
			ans.push_back(b);
		}
	}
	int B=ans[res-2];
	int fans=(qmi(10ll,A)+qmi(10ll,B))%mod;
    cout<<fans<<"\n";
}