[ARC178B] 1 + 6 = 7
题面翻译
统计满足 X + Y = Z X+Y=Z X+Y=Z 且 X , Y , Z X,Y,Z X,Y,Z 在十进制下分别是 a 1 , a 2 , a 3 a_1,a_2,a_3 a1,a2,a3 位数的三元组个数，方案数对 998244353 998244353 998244353 取模。
数据范围： a i ≤ 1 0 9 a_i\le 10^9 ai≤109
样例 #1
样例输入 #1
4
1 1 1
1 6 7
167 167 167
111 666 777
样例输出 #1
36
45
731780675
0
假设 a 1 ≤ a 2 a_1\le a_2 a1≤a2 。可以肯定的是 a 1 a_1 a1 位数加 a 2 a_2 a2 位数不可能的到位数小于 a 2 a_2 a2 或位数大于 a 2 + 1 a_2+1 a2+1 ，遇到时直接输出 0 0 0 。
我们令 t m p 1 tmp1 tmp1 为 a 1 a_1 a1 位数的个数， t m p 2 tmp2 tmp2 同理。
t m p 1 = 1 0 a 1 − 1 0 a 1 − 1 , t m p 2 = 1 0 a 2 − 1 0 a 2 − 1 tmp1=10^{a_1}-10^{a_1-1},tmp2=10^{a_2}-10^{a_2-1} tmp1=10a1−10a1−1,tmp2=10a2−10a2−1 。
分类讨论：
- 当 a 1 ≠ a 2 , a 3 = a 2 + 1 a_1\ne a_2,a_3=a_2+1 a1=a2,a3=a2+1 时， X X X 可以取该位数内任意的数，而 Y Y Y 仅可取 [ 1 0 a 3 − X , 1 0 a 3 − 1 ] [10^{a_3}-X,10^{a_3}-1] [10a3−X,10a3−1] 内的数。， a n s = ∑ i = 1 0 a 1 − 1 1 0 a 1 − 1 i = ( 1 0 a 1 − 1 + 1 0 a 1 − 1 ) × t m p 1 2 ans=\sum_{i=10^{a_1-1}}^{10^{a_1}-1}i=\frac{(10^{a_1-1}+10^{a_1}-1)\times tmp1}{2} ans=∑i=10a1−110a1−1i=2(10a1−1+10a1−1)×tmp1。
- 当 a 1 ≠ a 2 , a 3 = a 2 a_1\ne a_2,a_3=a_2 a1=a2,a3=a2 时，可通过计算补集， a n s = t m p 1 × t m p 2 − ∑ i = 1 0 a 1 − 1 1 0 a 1 − 1 i = t m p 1 × t m p 2 − ( 1 0 a 1 − 1 + 1 0 a 1 − 1 ) × t m p 1 2 ans=tmp1\times tmp2-\sum_{i=10^{a1-1}}^{10^{a1}-1}i=tmp1\times tmp2-\frac{(10^{a_1-1}+10^{a_1}-1)\times tmp1}{2} ans=tmp1×tmp2−∑i=10a1−110a1−1i=tmp1×tmp2−2(10a1−1+10a1−1)×tmp1。
- 当 a 1 = a 2 , a 3 = a 2 + 1 a_1=a_2,a_3=a_2+1 a1=a2,a3=a2+1 时，当 X ∈ [ 1 0 a 1 − 1 , 9 × 1 0 a 1 − 1 − 1 ] X\in[10^{a_1-1},9\times10^{a_1-1}-1] X∈[10a1−1,9×10a1−1−1] 时， Y ∈ [ 1 0 a 1 − X , 1 0 a 1 − 1 ] Y\in[10^{a_1}-X,10^{a_1}-1] Y∈[10a1−X,10a1−1] ， Y Y Y 共有 X X X 种取法。当 X ∈ [ 9 × 1 0 a 1 − 1 , 1 0 a 1 − 1 ] X\in[9\times10^{a_1-1},10^{a_1}-1] X∈[9×10a1−1,10a1−1] 时，由于 Y Y Y 可取的最小值为 1 0 a 1 − 1 10^{a_1-1} 10a1−1 ， X + Y ≥ 1 0 a 3 X+Y\ge10^{a_3} X+Y≥10a3 ，所以 Y Y Y 的取值有 t m p 2 tmp2 tmp2 种。所以 a n s = t m p 2 × 1 0 a 1 − 1 + ∑ i = 1 0 a 1 − 1 9 × 1 0 a 1 − 1 − 1 i = t m p 2 × 1 0 a 1 − 1 + ( 1 0 a 1 − 1 ) × ( 8 × 1 0 a 1 − 1 ) 2 ans=tmp2\times10^{a_1-1}+\sum_{i=10^{a_1-1}}^{9\times10^{a_1-1}-1}i=tmp2\times10^{a_1-1}+\frac{(10^{a_1}-1)\times(8\times10^{a_1-1})}{2} ans=tmp2×10a1−1+∑i=10a1−19×10a1−1−1i=tmp2×10a1−1+2(10a1−1)×(8×10a1−1) 。
- 当 a 1 = a 2 , a 3 = a 2 a_1=a_2,a_3=a_2 a1=a2,a3=a2 时，可通过计算补集， a n s = t m p 1 × t m p 2 − t m p 2 × 1 0 a 1 − 1 + ∑ i = 1 0 a 1 − 1 9 × 1 0 a 1 − 1 − 1 i = t m p 1 × t m p 2 − t m p 2 × 1 0 a 1 − 1 + ( 1 0 a 1 − 1 ) × ( 8 × 1 0 a 1 − 1 ) 2 ans=tmp1\times tmp2-tmp2\times10^{a_1-1}+\sum_{i=10^{a_1-1}}^{9\times10^{a_1-1}-1}i=tmp1\times tmp2-tmp2\times10^{a_1-1}+\frac{(10^{a_1}-1)\times(8\times10^{a_1-1})}{2} ans=tmp1×tmp2−tmp2×10a1−1+∑i=10a1−19×10a1−1−1i=tmp1×tmp2−tmp2×10a1−1+2(10a1−1)×(8×10a1−1) 。
code:
#include<bits/stdc++.h>
#define niyuan 499122177
#define mod 998244353
using namespace std;
long long ksm(long long a,long long b){
long long res=1;
while(b){
if(b&1) res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
long long a1,a2,a3,ans;
scanf("%lld%lld%lld",&a1,&a2,&a3);
if(a1>a2) swap(a1,a2);
if(a3<a2||a3>a2+1){
printf("0\n");
continue;
}
long long tmp1=9*ksm(10,a1-1)%mod;
long long tmp2=9*ksm(10,a2-1)%mod;
if(a1!=a2&&a3==a2+1) ans=(ksm(10,a1-1)+ksm(10,a1)-1)%mod*tmp1%mod*niyuan%mod;
else if(a1!=a2&&a3==a2) ans=(tmp1*tmp2%mod-(ksm(10,a1-1)+ksm(10,a1)-1)%mod*tmp1%mod*niyuan%mod+mod)%mod;
else if(a1==a2&&a3==a2+1) ans=(tmp2*ksm(10,a1-1)%mod+(ksm(10,a1)-1)%mod*8%mod*ksm(10,a1-1)%mod*niyuan%mod)%mod;
else ans=(tmp1*tmp2%mod-(tmp2*ksm(10,a1-1)%mod+(ksm(10,a1)-1)%mod*8%mod*ksm(10,a1-1)%mod*niyuan%mod)%mod+mod)%mod;
printf("%lld\n",ans);
}
return 0;
}