Codeforces gym 10025K: 2011-2012 Petrozavodsk Summer Training Camp, Kyiv + Kharkov NU Contest

Problem
Little Petya likes to draw on the walls a lot. He spent a lot of time, writing down all the integers from 1 to 10k , inclusive, in a row. After he had finished, he decided to show this masterpiece to his friend Masha. The only thing she wondered was the number of zeroes written on the wall. Help Petya to answer her question. Since this number can be very large, output it modulo p , otherwise the children will be scared.
Limits
TimeLimit(ms):2000
MemoryLimit(MB):256
k∈[1,1018]
p∈[1,109]
Look up Original Problem From here
Solution
둥지들은 [1,10],[10100],[1001000]...이런 구간에 0의 개수, [1,10)에 0개,[10100]에 9개,[1001000]에 180개,[103104)에 2700개,[104105)에 36000개...(작은 프로그램으로 표를 쓰면 알 수 있다)
상기 숫자가 통항 공식을 충족시키는 것을 발견하다 an=9(n-3.1)×10n−2
그럼,ans=(∑ki=19(i-3.1)×10i-4-2)+k(구간을 열기 때문에 k를 하나 더 추가해야 한다).
착위상감법으로 Sk=∑ki=1(i -3) 구하다×10i−2:
Sk=(1−1)×10−1+(2−1)×100+…+(k−2)×10k−3+(k−1)×10k−2
10Sk=(1−1)×100+…+(k−3)×10k−3+(k−2)×10k−2+(k−1)×10k−1
Sk−10Sk=−9Sk=100+101+…+10k−2−(k−1)×10k−1=1×(1−10k−1)1−10−(k−1)×10k−1
9Sk=(k -3.1)×10k−1−10k−1−19
그래서 ans=(k --1)×10k−1−10k−1−19+k
첫 번째 항목은 빠른 멱으로 구할 수 있고 두 번째 항목은 제법이 있어서 모형을 추출하여 연산할 수 없지만 두 번째 항목은 실제적으로 111과 같다는 것을 발견하였다.의 수는 1만 포함하고 빠른 멱으로 구할 수 있다.
Complexity
TimeComplexity:O(log2k)
MemoryComplexity:O(1)
My Code

//Hello. I'm Peter.
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define peter cout<<"i am peter"<<endl
#define input freopen("data.txt","r",stdin)
#define randin srand((unsigned int)time(NULL))
#define INT (0x3f3f3f3f)*2
#define LL (0x3f3f3f3f3f3f3f3f)*2
#define gsize(a) (int)a.size()
#define len(a) (int)strlen(a)
#define slen(s) (int)s.length()
#define pb(a) push_back(a)
#define clr(a) memset(a,0,sizeof(a))
#define clr_minus1(a) memset(a,-1,sizeof(a))
#define clr_INT(a) memset(a,INT,sizeof(a))
#define clr_true(a) memset(a,true,sizeof(a))
#define clr_false(a) memset(a,false,sizeof(a))
#define clr_queue(q) while(!q.empty()) q.pop()
#define clr_stack(s) while(!s.empty()) s.pop()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define pi 3.1415926535898
#define eps 1e-9
#define MOD 1000000007
#define MAXN 2015
#define N
#define M
ll k,p,ans;
inline ll quick_power(ll x,ll y){
    if(y==0) return 1LL;
    ll res=quick_power(x,y>>1);
    if(y%2==0) return res*res%p;
    else return res*res%p*x%p;
}
ll oneoneone(ll n){
    if(n==0) return 0;
    if(n==1) return 1LL;
    ll n1=n>>1;
    ll right=oneoneone(n1);
    ll left=right;
    if(n%2LL==1LL) left=(left*10LL+1LL)%p;
    left=left*quick_power(10LL,n1)%p;
    return (left+right)%p;
}
int main(){
    freopen("zeroes.in","r",stdin);
    freopen("zeroes.out","w",stdout);
    cin>>k>>p;
    ans=(((k-1)%p)*quick_power(10LL,k-1)%p+(k%p))%p;
    ans=ans-oneoneone(k-1);
    ans=(ans%p+p)%p;
    cout<<ans<<endl;
}