URAL 1749 Periodic Sum (二分法 + 溢出處理)

題目大意：

給出 p ， p是一個很大的數，其位數在10^5位以内，定義S( t )為一個整數中去任意的連續 i 位得到的數的和， i 從1到 t 的長度

比如 t = 1025時， S(1025) = 1 + 0 + 2 + 5 + 10 + 02 + 25 + 102 + 025 + 1025 = 1575

定義F( t , k ) 為将 t 重複寫 k 次得到的新的數， 比如 F( 1025 , 3 ) = 102510251025

現在要求求出 S( F( p , k ) )

輸入給出 p, k ,m 要求輸出 S( F( p , k ) ) mod m;

大緻思路：

首先這道題求出 S ( F( p , k ) ) 的通項是不友善取模的，這裡寫出我的計算過程：

先考慮沒有 k 次重複的情況， 對于一個數 p ，先來求 S( p )

将數 p 用字元串儲存之後得到每一位的數字

設s[1] ~ s[len] 依次是數 p 的最低位到最高位， len 是字元串 p  的長度

那麼 對于從低到高的第 i 位的數 s[ i ] 在和 S( p ) 中出現的情況如下：

s[1]作為個位出現 len 次

s[2] 作為個位出現 len - 1 次， 作為十位出現 len - 1次

s[3] 作為個位出現 len - 2次， 作為十位出現 len - 2 次， 作為百位出現 len - 3次

.....

這個很容易證明，這裡不給出證明，自己畫一下就明白了

 s[ i ] 作為個位出現 len - i + 1次，作為十位出現 len - i + 1次....作為數級是 10^(i - 1)  的位出現 len - i + 1次

那麼對于數 p , 設其長度為 len , 從最低位到最高位的數依次是 s[1] ~ s[len]

那麼：

那麼這裡到 p 重複 k 次時的情況便是 len 變為k*len而 p 這個數變成重複k次得到的數

那麼便有 s[ i + c*len ]  = s[ i ]， c 從0到 k - 1

然後由于本題中資料範圍很大，最後的結果是取模 m 輸出

那麼由于分母有一個9， 取的模并不保證是一個質數，也就不能使用費馬小定理轉換

注意到分子一定能被9整除，可以發現這樣一個事實：

對于整數A有  A mod B = ((9*A) mod (9*B)) / 9;

這是一個很容易證明的結論，證明如下：

設 A = a*B +b;

那麼 A mod B = b 

9*A mod(9*B) = (9*a*B +9*b) mod (9*B) = 9*b

是以 A mod B = ((9*A) mod (9*B)) / 9;

也就是說 對于S(p) % m， 我們可以求 (S(p) * 9) % (9*m) 将最後的結果除以9即可

那麼我們現在可以不考慮分母9的問題，但是這樣做會造成一個隐患，由于現在取模m 變成了取模 9*m， 對于兩個小于 9*m的數相乘範圍在 1.8*10^19内，超出了long long 的範圍， 這樣便不能直接将兩個long long型在9*m範圍内的數直接相乘取模，這裡用到一個方法，代碼和快速幂相似，成功避免了兩個數直接乘超出資料範圍的情況，主要思想是将一個long long拆成多個數來一次相乘将得到的結果相加取模，避免溢出，具體見代碼中的 mul 函數部分

那麼繼續将這個公式推至S( F( p, k) ) 的形式：

現在來看最後的這個式子，變量 i 從1到 len 可以直接循環 (len <= 100000)

剩下的就是兩個求和式的問題，對于sigma(base^i)  i 從0 到 k-1 可以每次二分來求

用Geo(base, pow) 表示 sigma(base^i) i 從0 到pow - 1 有

Geo(base, 0) = 1;

Geo(base, pow) = Geo(base, pow - 1) + base^(pow - 1) (pow 是奇數時)

Geo(base, pow) = Geo(base, pow / 2) * ( 1 + base^(pow / 2)) (pow 是偶數時)

這個做法在之前寫的 Codeforces 327C Magic Five那道題求等比數列的和的時候也用到過

那麼對于sigma( i * base^i ) i 從0 到 pow - 1來說也可以用二分來求

用AriGeo(base, pow) 表示sigma( i * base^i ) i 從0 到pow - 1有：

AriGeo(base, 0) = 0;

AriGeo(base, pow) = AriGeo(base, pow - 1) + (pow - 1)*base^(pow - 1) (pow 是奇數時)

AriGeo(base, pow) = AriGeo(base, pow ./ 2)(1 + base^(pow./ 2)) + (pow / 2) * (base^(pow / 2)) * Geo(base, pow / 2)  (pow 是偶數時)

上面這個式子可以自己驗證一下

對于每一個求幂的式子，都用快速幂的方法來求

這樣整個複雜度便降下來了，注意在減法操作之後加上要取模的數之後取模，防止負數出現

整個思路和注意的要點都已經說完了，接下來是代碼：

Result  :  Accepted     Memory  :  2021 KB     Time  :  875 ms

/*
 * Author: Gatevin
 * Created Time:  2014/7/27 11:10:56
 * File Name: test.cpp
 */
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

char ss[100010];
lint s[100010];
lint k,m,mod,len;
lint ten[100010];

lint mul(lint a, lint b)
{
    lint ret = 0;
    while(b)
    {
        if(b & 1)
        {
            ret = (ret + a) % mod;
        }
        b >>= 1;
        a= (a*2) % mod;
    }
    return ret;
}

lint quick_pow(lint base, lint pow)
{
    lint ret = 1;
    while(pow)
    {
        if(pow & 1)
        {
            ret = mul(ret, base);
        }
        pow >>= 1;
        base = mul(base, base);
    }
    return ret;
}

//Evaluate the sum of geometric sequence sigma(base^i) , i range from 0 to pow - 1
lint GeoSeq(lint base, lint pow)
{
    if(pow == 1) return 1;
    if(pow & 1) return (GeoSeq(base, pow - 1) + quick_pow(base, pow - 1)) % mod;
    else return mul(GeoSeq(base, pow >> 1), (1 + quick_pow(base, pow >> 1)) % mod);
}

/* 
 * Evaluate the sum of the sequence which is a combination of 
 * an arithmetic sequence and a geomatric sequence sigma(i*base^i), i range from 0 to pow - 1
 */
lint AriGeoSeq(lint base, lint pow) 
{
    if(pow == 1) return 0;
    if(pow & 1) return (AriGeoSeq(base, pow - 1) + mul(pow - 1, quick_pow(base, pow - 1))) % mod;
    else return (mul(AriGeoSeq(base, pow >> 1), 1 + quick_pow(base, pow >> 1))
                + mul(mul(pow >> 1, quick_pow(base, pow >> 1)), GeoSeq(base, pow >> 1))) % mod;
}

lint solve()
{
    lint answer = 0;
    ten[0] = 1;
    for(int i = 1; i <= len; i++)
    {
        ten[i] = (ten[i - 1] * 10) % mod;
    }
    lint tmp1 = GeoSeq(ten[len], k);
    lint tmp2 = AriGeoSeq(ten[len], k);
    lint tmp3 = (k*(k - 1)/2) % mod;
    for(int i = 1; i <= len; i++)
    {
        answer = (answer + mul(s[i], (mul(mul(tmp1, (k*len - i + 1) % mod), ten[i]) - mul((k*len - i + 1) % mod, k)
                        - mul(mul(tmp2, len), ten[i]) + mul(len, tmp3) + 2*mod) % mod)) % mod;
    }
    return answer;
}

int main()
{
    scanf("%s",ss);
    scanf("%I64d%I64d",&k,&m);
    mod = 9*m;
    len = strlen(ss);
    for(int i = 0; i <= len - 1; i++)
    {
        s[len - i] = ss[i] - '0';
    }
    lint answer = solve();
    cout<<answer/9<<endl;
    return 0;
}