[ABC322G] Two Kinds of Base

发布时间 2023-10-06 19:21:21作者: Semorius

第一次赛后马上AK ABC,好激动,感觉是这场太水了,一看评分,G有2800?!

感觉这个 Trick 挺有用的:某些变量真正能取到的值其实远远没有给的范围那么大,除了某些特殊情况,而这些特殊情况可以用特殊的方式统计答案。

题意

对于一个非负整数序列 \(S=(S_1,S_2,\dots,S_k)\) 和一个整数 \(a\),定义函数 \(f(S,a)\) 如下:

\[f(S,a) = \sum_{i=1}^{k} S_i \times a^{k - i} \]

给定正整数 \(N\)\(X\)。求满足以下所有条件的非负整数序列 \(S=(S_1,S_2,\dots,S_k)\) 和正整数 \(a\)\(b\) 的三元组 \((S,a,b)\) 的数量模 \(998244353\)

  • \(k \ge 1\)
  • \(a,b \le N\)
  • \(S_1 \neq 0\)
  • \(S_i < \min(10,a,b)(1 \le i \le k)\)
  • \(f(S,a) - f(S,b) = X\)

思路