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

            久久婷婷久久一区二区三区| 激情久久久久久久久久| 久久亚洲国产午夜精品理论片| 色狠狠久久AV五月综合| 69久久夜色精品国产69| 久久久久九国产精品| 国产精品无码久久综合| 99久久精品久久久久久清纯| 亚洲欧美国产精品专区久久| 无码精品久久久久久人妻中字| 伊人久久免费视频| 天天做夜夜做久久做狠狠| 欧美精品一区二区精品久久| 国产成人精品久久一区二区三区av | 亚洲国产精品成人久久| 久久青草国产手机看片福利盒子| 老司机午夜网站国内精品久久久久久久久| 男女久久久国产一区二区三区| 久久国产精品一区二区| 久久国产精品成人影院| 久久天天躁夜夜躁狠狠| 国产激情久久久久影院小草| 久久国语露脸国产精品电影| 伊人久久大香线蕉精品| 久久精品亚洲日本波多野结衣| 久久亚洲欧洲国产综合| 好久久免费视频高清| 波多野结衣AV无码久久一区| 久久无码专区国产精品发布 | 久久综合五月丁香久久激情| 久久精品国产91久久麻豆自制| 久久久久久久久波多野高潮| 久久国产视屏| 久久精品国产亚洲Aⅴ香蕉| 97久久精品人人澡人人爽| 久久精品国产精品青草| 国产精品久久精品| 日韩精品久久久久久| 久久亚洲精品中文字幕三区| 久久九九青青国产精品| 国产ww久久久久久久久久|