注意 P P P事实上不会影响复杂度，因为关于组合数，我们有一个非常经典的结论： ( n + m m ) \binom{n+m}{m} (mn+m)包含的 P P P的幂的次数等于 n n n和 m m m在 P P P进制下做加法的进位次数。这样，我们只需要关心进位的次数，而不必知道每一位具体是多少。
这个结论的证明也不困难。考虑答案是 ∑ i ≥ 1 ⌊ n + m p i ⌋ − ⌊ n p i ⌋ − ⌊ m p i ⌋ \sum_{i\ge 1}\lfloor\frac{n+m}{p^i}\rfloor-\lfloor\frac{n}{p^i}\rfloor-\lfloor\frac{m}{p^i}\rfloor ∑i≥1⌊pin+m⌋−⌊pin⌋−⌊pim⌋，那么只要在第 i i i位进位了就会贡献 1 1 1，所以就证完了。
感觉我在废话。。。但是我们也可以顺便发现，答案肯定不会超过 ∣ A ∣ |A| ∣A∣，所以 α \alpha α的范围也是假的。
传统的数位 D P DP DP都是从高往低位处理，但是这题不一样，因为涉及到进位所以似乎从低往高位处理会更自然一些，所以数位 D P DP DP的方向其实是都可以的，总之用一个 01 01 01状态记录一下就好了。还要用 01 01 01状态记录一下是否进位，然后记录一下进位的次数，这道题目就做完了。
复杂度 O ( ∣ A ∣ 2 ) O(|A|^2) O(∣A∣2)。文章来源：https://www.toymoban.com/news/detail-532928.html
需要把 A A A转化成 P P P进制。这个直接模拟高精就行了，因此不再赘述。文章来源地址https://www.toymoban.com/news/detail-532928.html
到了这里，关于【学习笔记】CF582D Number of Binominal Coefficients的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
