• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            coreBugZJ

            此 blog 已棄。

            EOJ 1851. Summing Sums 的三種巧妙解法

            Summing Sums

            Time Limit:1000MSMemory Limit:30000KB
            Total Submit:408Accepted:86

            Description

            The N (1 <= N <= 50,000) cows, conveniently numbered 1..N, are trying to learn some encryption algorithms. After studying a few examples, they have decided to make one of their own! However, they are not very experienced at this, so their algorithm is very simple:
            Each cow i is given a starting number C_i (0 <= C_i < 90,000,000),and then all the cows perform the following process in parallel:
            * First, each cow finds the sum of the numbers of the other N-1 cows.
            * After all cows are finished, each cow replaces her number with the sum she computed. To avoid very large numbers, the cows will keep track of their numbers modulo 98,765,431.

            They told Canmuu the moose about it in November; he was quite impressed.

            Then one foggy Christmas Eve, Canmuu came to say:
            "Your algorithm is too easy to break! You should repeat it T(1 <= T <= 1,414,213,562) times instead."

            Obviously, the cows were very frustrated with having to perform so many repetitions of the same boring algorithm, so after many hours of arguing, Canmuu and the cows reached a compromise: You are to calculate the numbers after the encryption is performed!

            *Some extra feedback will be provided for the first 10 submissions to this problem.

            Input

            * Line 1: Two space-separated integers: N and T
            * Lines 2..N+1: Line i+1 contains a single integer: C_i

            Output

            * Lines 1..N: Line i contains a single integer representing the number of cow i (modulo 98,765,431) at the end of the encryption.

            Sample Input

            3 4
            1
            0
            4

            INPUT DETAILS:
            Three cows, with starting numbers 1, 0, and 4; four repetitions of the encryption algorithm.

            Sample Output

            26
            25
            29

            OUTPUT DETAILS:
            The following is a table of the cows' numbers for each turn:Cows' numbers


            Turn Cow1 Cow2 Cow3
            0 1 0 4
            1 4 5 1
            2 6 5 9
            3 14 15 11
            4 26 25 29

             

            Source

            usaco 07CHN



            ----------------------------------------------------------------------------------------
            解法一:

            令 cs = c[1] + c[2] + ... + c[n-1] + c[n];
            令 a[t][i] = 處理 t 次后的c[i];
            令 s[t] = a[t][1]+a[t][2]+a[t][3] + … + a[t][n]


            t = 0 時(shí),
            s[0] = cs = (n-1)^0 * cs
            a[0][i] = c[i]


            t = 1 時(shí),
            s[1] = (n-1)*s[0] = (n-1)^1  * cs
            a[1][i] = s[0] – a[0][i] = (n-1)^0 * cs – c[i]


            t = 2 時(shí),
            s[2] = (n-1)*s[1] = (n-1)^2  * cs
            a[2][i] = s[1] – a[1][i] = ((n-1)^1-(n-1)^0)*cs + c[i]

            t = 3 時(shí),
            s[3] = (n-1)*s[2] = (n-1)^3  * cs
            a[3][i] = s[2] – a[2][i] = ((n-1)^2 – (n-1)^1 + (n-1)^0) * cs – c[i]


            結(jié)論:

            a[t][i] = [ (n-1)^(t-1) – (n-1)^(t-2) + (n-1)^(t-3) - … (n-1) ^ 0 ] * cs  +  (-1)^t * c[i]


            令 ns = (n-1)^(t-1) - (n-1)^(t-2) + (n-1)^(t-3) - (n-1)^(t-4) ... (n-1)^(0)


            則 a[t][i] = ns * cs + (-1)^t * c[i]



            求 ns 時(shí),使用二分法,求等比數(shù)列的和。


            解法一代碼




            ----------------------------------------------------------------------------------------
            解法二:

            分析同上,只是
            求 ns 時(shí),使用等比數(shù)列求和公式。

            對(duì)于除法之后再取余的問題,zyd 教了我一個(gè)技巧。

            解法二代碼




            ----------------------------------------------------------------------------------------
            解法三:

            模擬實(shí)際的變換過程,但是通過二分法加速。

            構(gòu)造矩陣


            A =

            [ -1   1  ]
            |         |
            [ 0   n-1 ]

             

            [ Ci ]          [ Ci ]
            |    | = A^t  * |    |
            [ CS ]          [ CS ]


            其中,A^t 可以二分。


             

            posted on 2012-02-29 16:46 coreBugZJ 閱讀(605) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè)

            久久精品国产男包| 久久se精品一区精品二区| 久久久WWW免费人成精品| 精品99久久aaa一级毛片| 国产综合免费精品久久久| 久久er国产精品免费观看8| 久久久久噜噜噜亚洲熟女综合| 久久无码AV中文出轨人妻| 久久免费看黄a级毛片| 色综合久久综精品| 久久精品国产亚洲AV久| 一本久久久久久久| 久久亚洲精精品中文字幕| 天天爽天天爽天天片a久久网| 亚洲国产天堂久久久久久| 精品久久久久久久久午夜福利| 久久久久一级精品亚洲国产成人综合AV区| 久久免费视频1| 国产精品美女久久久网AV| 一本色道久久88—综合亚洲精品| 久久伊人精品青青草原高清| 亚洲午夜久久久影院伊人| 狠狠色丁香久久婷婷综合_中| 天天爽天天爽天天片a久久网| 亚洲精品无码久久久久sm| 蜜桃麻豆www久久国产精品| 99久久国产亚洲高清观看2024 | 国内精品九九久久精品| 久久久久亚洲AV成人网| 久久精品国产影库免费看 | 亚洲天堂久久久| 免费精品久久久久久中文字幕 | 欧洲性大片xxxxx久久久| 人人狠狠综合久久亚洲婷婷| 日本人妻丰满熟妇久久久久久| 99久久香蕉国产线看观香| 亚洲国产天堂久久久久久| 亚洲а∨天堂久久精品9966| 久久亚洲国产精品123区| 欧美久久亚洲精品| 一级a性色生活片久久无|