Atcoder357 D（逆元和快速幂）

Atcoder357 D

D

题意就是求给定一个数n的连续n个n相拼接，求最后的数\(mod998244353\)的值。
我们假设n的长度为len,那么n个n相拼接可以看成n*(\(10^{len^0}\)+\(10^{len^1}\)+....+\(10^{len^{n-1}}\))。那个就可以利用高中等比数列的知识求出公式（\(n*(10^{len^n}-1\))/(\(10^{len}\)-1)）。由于本身数字范围过大，不能直接求解，所以可以运用取mod运算乘法性质来求解。
但是取mod运算法则对除法没法很好的处理，所以这里需要用到逆元来将除法运算转换成乘法运算。
对于数字非常大，再求n次幂时也需要用到快速幂来降低时间复杂度。

乘法逆元

概念(视频)。
oiwiki的其他拓展

快速幂

oiwiki.

#include <bits/stdc++.h>
#define debug1(X) std::cout << #X << ": " << X << '\n'
#define debug2(X) std::cout << #X << ": " << X << ' '
using LL = long long;
const LL mod=998244353;
LL poww(LL a, LL b) {
     LL ans = 1, base = a;
     while (b != 0) {
         if (b & 1 != 0)
             ans =ans*base%mod;             
             base = base*base%mod;
             b >>= 1;
    }
     return ans;
 }
void solve()
{  
    
    LL n;
    std::cin>>n;
    LL num=n;
    LL len=1;
    while(num){
        num/=10;
        len=len*10;
    }
    LL ans=(n%mod)*(poww(len%mod,n)-1)%mod*(poww((len-1)%mod,mod-2))%mod;
   std::cout<<ans<<"\n";

}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}