• <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无码西西人体| 久久亚洲AV成人出白浆无码国产 | 久久天天婷婷五月俺也去| 青青久久精品国产免费看| 亚洲国产成人精品无码久久久久久综合| 久久e热在这里只有国产中文精品99 | 日韩一区二区三区视频久久| 7777精品久久久大香线蕉| 91精品国产91久久久久福利| 久久夜色撩人精品国产| 久久香蕉超碰97国产精品 | 日韩乱码人妻无码中文字幕久久 | 久久精品亚洲精品国产色婷| 亚洲欧美精品一区久久中文字幕| 国产亚洲综合久久系列| 色妞色综合久久夜夜| 欧美午夜A∨大片久久| 日韩亚洲欧美久久久www综合网| 久久99国产综合精品| 性高湖久久久久久久久AAAAA| 久久国产乱子伦精品免费强| a级成人毛片久久| 久久天天婷婷五月俺也去| 成人亚洲欧美久久久久| 精品人妻伦一二三区久久| 国产亚洲欧美精品久久久| 亚洲欧美伊人久久综合一区二区 | 国产精品中文久久久久久久| 青青草原综合久久大伊人| 99久久国产免费福利| 一本伊大人香蕉久久网手机| 99国产欧美久久久精品蜜芽| MM131亚洲国产美女久久| 久久AV高清无码| 久久亚洲欧美国产精品 | 亚洲AV无码久久精品色欲 | 精品无码久久久久久国产| 免费精品99久久国产综合精品| 久久精品国产亚洲av影院| 国产精品一区二区久久不卡|