Problem 11609 Teams

此題要求出某數字排序在最前面在的次數。

例如 2，可以分成
1 => 1, 12.
2 => 2, 21. 總共 4 次。
而 3，可以分成
1 => 1, 12, 13, 123.
2 => 2, 21, 23, 213.
3 => 3, 31, 32, 312. 總共 12 次。

可以找出公式為 p(n) = n * 2^n-1。每個數值都要 mod 1000000007 才為答案。
假設我們要找出 p(100) 的值，則為 (100 * 2⁹⁹⁹) % 1000000007 = (100 * ( ( 2¹⁰⁰ % 1000000007 )⁹ % 1000000007) * ( ( 2¹⁰ % 1000000007 )⁹ % 1000000007) * ( ( 2¹ % 1000000007 )⁹ % 1000000007) ) % 1000000007。
其實以上分解看不懂沒有關係，重點是我們要先找出 2¹ % 1000000007、2¹⁰ % 1000000007、.....、2^1000000000 % 1000000007 的數值，再將讀入 n 值利用以上分解的方式去找出答案。
所以宣告一個陣列 p[10] 裡面擺入 2¹ % 1000000007、2¹⁰ % 1000000007、.....、2^1000000000 % 1000000007 數值。 C 語言程式碼如下：

long long int p[10] = { 2, 1024, 976371285, 688423210, 905611805,
607723520, 235042059, 255718402, 494499948, 140625001};

而再主程式計算答案的程式碼如下：

int n, i, k, l;
long long int ans, tmp, m, copyM, j;
scanf("%d", &n);
for (i = 1; i <= n; i ++)
{
    ans = 1;
    scanf("%lld", &m);
    copyM = m;
    m --;
    for (j = 1000000000, k = 9; j > 0; j /= 10, k --)
    {
        tmp = m / j;
        m %= j;
        if (tmp)
        {
            while (tmp --)
                ans = ( ans * p[k]) % 1000000007;
        }
    }
    
    ans = (ans * copyM) % 1000000007;
    printf("Case #%d: %lld\n", i, ans);
}

By David.K

p11609題目連結
回ACM題庫目錄
回首頁