2014-07-06

UVa 12042 - Colorful Eggs

1. Problem
2. Input
3. Sample Input
4. Sample Output
5. Solution

Problem

Little Mou is very fond of eggs. She has n baskets for keeping her colorful eggs. Each basket contains eggs of different colors. The baskets are numbered from 1 to n. She has a strange hobby about these eggs. On each day, she takes each basket starting from the nth basket. When she is doing this for basket i, she counts all eggs placed in baskets 1 to i (inclusive) and takes their sum. Let this value of sum be counti. She removes all old eggs from the ith basket and keeps counti new eggs in the ith basket. After that she puts all the old eggs of the ith basket in the (i-1)th basket removing the old eggs of the (i-1)th basket. As Mou is very fond of eggs, she eats all old eggs of the (i-1)th basket. And when she has finished eating, she repeats the work for this (i-1)th basket. If she reaches the 1st basket, she stops her work and doesn’t eat any more eggs and goes to sleep!

For example let Mou has 3 baskets at day 1. 1st basket contains 1 egg, 2nd basket contains 1 egg and the 3rd basket contains 2 eggs.

So simulation for day 3 follows:

Basket Index => 3 2 1

….. 略

Now the problem is given n, d and the number of eggs in each basket eggi, your job is to find the number of eggs in each basket after d days. As the number can be very big output answer modulo 1,000,000,007.

Input

The first line of the input file contains an integer T (T ≤ 111) which denotes the total number of test cases. The description of each test case is given below:

Two integers N (1 ≤ n ≤ 60) and d (1 ≤ d ≤ 1,000,000,000), followed by n integers denoting the number of eggs in each basket starting from 1 to n.
Output

For each test case print one line of output containing the number of eggs in each basket after d days have passed separated by single spaces between them. See the sample output for more details. As the numbers can be very big output answer modulo 1,000,000,007.

Sample Input

Sample Output

1
2
3

129 189 277
5 9
1 10

Solution

題目描述：

一開始有 n 籃雞蛋，每一籃有各自個雞蛋數量。

每一次的操作從最右邊 (編號大的那籃開始) 進行，將所有比它小的編號的雞蛋總數加到這一籃，並且將原本的雞蛋總數指派給下一個籃。

問第 d 天後的結果。

題目解法：

建造轉移矩陣，使用 D&C 完成。

觀察一下可以發現，矩陣肯定長成這副德性

[1, 1, 1, ..., 1, 1, 1]
[1, 0, 1, ..., 1, 1, 1]
[1, 0, 0, 1, ..., 1, 1] = M
[1, 0, 0, 0, ..., 1, 1]
...
[1, 0, 0, 0, ..., 0, 0]
[an]
[an-1]
[an-2] = A(1)
...
[a1]
M x A(1) = A(2)
M x M x A(1) = A(3)

#include <stdio.h> 
#include <string.h>
const long long mod = 1000000007LL;
struct Matrix {
    long long v[64][64];
    int row, col; // row x col
    Matrix(int n, int m, long long a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++)
            for(int j = 0; j < x.col; j++)
                for(int k = 0; k < col; k++)
                    ret.v[i][j] += v[i][k] * x.v[k][j] %mod,
                    ret.v[i][j] %= mod;
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
};
int main() {
    int testcase, n, d, a[105];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &d);
        d--;
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        Matrix x(n, n), A(n, 1);
        for(int i = 0; i < n; i++)
            A.v[i][0] = a[n-i-1];
        for(int i = 0; i < n; i++)
            x.v[0][i] = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                x.v[i][j] = 1;
            }
            x.v[i][0] = 1;
        }
        Matrix y = x ^ d;
        Matrix r = y * A;
        for(int i = r.row-1; i >= 0; i--) { 
            printf("%lld", r.v[i][0]);
            if(i)	putchar(' ');
        } 
        puts("");
    }
    return 0;
}

Morris' Blog