atcoder ABC 357-D题详解

atcoder ABC 357-D题详解

Problem Statement

For a positive integer N, let VN​ be the integer formed by concatenating N exactly N times.
More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get VN​.
For example, V3​=333 and V10​=10101010101010101010.

Find the remainder when VN​ is divided by 998244353.

Constraints

1≤N≤1018
N is an integer.

Input

The input is given from Standard Input in the following format:

N

Output

Print the remainder when VN​ is divided by 998244353.

Sample Input 1

5

Sample Output 1

55555
The remainder when V5​=55555 is divided by 998244353 is 55555.

Sample Input 2

9

Sample Output 2

1755646
The remainder when V9​=999999999 is divided by 998244353 is 1755646.

Sample Input 3

10000000000

Sample Output 3

468086693
Note that the input may not fit into a 32-bit integer type.

思路分析1：

暴力直接写，re和tle

code：

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
string s;
vector<string>v;
ll n;
int main(){cin>>s;//s本来就有一个，所以后面要减1ll n=stoll(s);for(ll i=0;i<n-1;i++){v.push_back(s);}for(ll i=0;i<n-1;i++){s=s+v[i];}ll cnt=stoll(s);cnt=cnt%998244353;cout<<cnt;
}

思路分析2:

本题使用快速幂，先拼接，可以发现是等比数列，然后使用等比数列求和公式，因为数太大会爆ll，所以使用欧拉定理和费马小定理分别化简式子来优化时间复杂度，最后答案也要先mod后乘，不然会爆ll。

code：

#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll n;
int qpow(int a,int n){//不用欧拉定理应该为ll nint res=1;while(n){if(n&1) res=1ll*res*a%mod;a=1ll*a*a%mod;n>>=1;}return res;
}
int getlen(ll n){int ans=0;while(n){ans++;n/=10;}return ans;
}
int main(){cin>>n;int l=getlen(n);int c1=qpow(10,n%(mod-1)*l%(mod-1))-1;//n*l会爆ll所以要分别先mod//不用欧拉定理c1=qpow(10,qpow(10,l),n)-1;int c2=qpow(10,l)-1;c2=qpow(c2,mod-2);int ans=1ll*n%mod*c1%mod*c2%mod;cout<<ans;return 0;
}