• <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è)

            亚洲欧美久久久久9999| 午夜精品久久久内射近拍高清| 无码人妻久久一区二区三区免费| 久久精品无码专区免费东京热| 亚洲va久久久噜噜噜久久狠狠 | 久久久久久亚洲精品影院| 久久99免费视频| 久久久久久狠狠丁香| 婷婷国产天堂久久综合五月| 少妇久久久久久被弄到高潮| 99久久精品国产一区二区三区| 女同久久| 99久久国产综合精品五月天喷水| 久久久久久精品免费免费自慰| 亚洲嫩草影院久久精品| 亚洲AV无码久久精品狠狠爱浪潮| 国产精品无码久久四虎| 久久综合亚洲欧美成人| 久久夜色精品国产| 精品久久久久久国产三级| 国产午夜福利精品久久2021| 中文字幕无码久久久| 久久久受www免费人成| 久久国产亚洲精品麻豆| 91精品国产综合久久婷婷| 亚洲香蕉网久久综合影视 | 97精品伊人久久久大香线蕉 | 精品无码久久久久久久久久| 久久天天躁狠狠躁夜夜网站| 久久国产AVJUST麻豆| 久久这里有精品视频| 久久伊人色| 久久综合久久性久99毛片| 国产高潮久久免费观看| 99热成人精品免费久久| 一本色道久久88加勒比—综合| 久久久女人与动物群交毛片| 久久久无码精品亚洲日韩按摩 | 久久综合综合久久狠狠狠97色88| 精品人妻久久久久久888| 91视频国产91久久久|