青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 時,
s[0] = cs = (n-1)^0 * cs
a[0][i] = c[i]


t = 1 時,
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 時,
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 時,
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]


結論:

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 時,使用二分法,求等比數列的和。


解法一代碼




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

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

對于除法之后再取余的問題,zyd 教了我一個技巧。

解法二代碼




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

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

構造矩陣


A =

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

 

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


其中,A^t 可以二分。


 

posted on 2012-02-29 16:46 coreBugZJ 閱讀(610) 評論(0)  編輯 收藏 引用 所屬分類: ACMAlgorithm 、課內作業

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品女主播在线观看| 久久久亚洲成人| 国产精品mv在线观看| av成人手机在线| 亚洲精品在线二区| 国产精品日韩一区二区三区| 亚洲影院在线观看| 亚洲欧美日韩一区| 在线观看久久av| 欧美成人视屏| 欧美另类在线观看| 香蕉尹人综合在线观看| 亚洲欧美卡通另类91av| 黄色成人小视频| 亚洲精品国产品国语在线app| 欧美国产视频日韩| 亚洲天堂免费观看| 午夜精品一区二区三区在线视 | 激情欧美日韩一区| 亚洲第一网站| 国产精品久久福利| 欧美成人免费va影院高清| 欧美日韩一区二区免费在线观看| 香蕉久久夜色| 欧美国产激情二区三区| 小黄鸭视频精品导航| 欧美va天堂在线| 久久爱www| 欧美国产日韩一区二区| 久久精品国产精品亚洲综合| 欧美国产第一页| 久久九九精品99国产精品| 欧美精品一区二| 久久久亚洲国产天美传媒修理工 | 狠狠色综合网站久久久久久久| 欧美国产激情二区三区| 国产精品综合| 亚洲精品久久久久| 在线观看日产精品| 亚洲欧美激情视频| 一区二区三区国产在线| 老司机精品视频一区二区三区| 午夜精品久久久久影视| 欧美精品日韩一本| 美女在线一区二区| 国产综合第一页| 亚洲欧美影音先锋| 亚洲午夜精品网| 欧美不卡高清| 你懂的亚洲视频| 黄色一区二区三区| 小黄鸭精品aⅴ导航网站入口| 亚洲视频在线一区| 欧美麻豆久久久久久中文| 你懂的视频一区二区| 狠狠色丁香婷综合久久| 欧美一区二区女人| 小黄鸭精品aⅴ导航网站入口| 欧美日韩亚洲国产精品| 91久久精品国产91久久性色| 极品av少妇一区二区| 欧美一区二区三区久久精品茉莉花 | 亚洲欧美日韩系列| 午夜在线一区二区| 国产精品卡一卡二卡三| 亚洲婷婷在线| 欧美亚洲视频在线看网址| 欧美性事在线| 亚洲一区视频在线| 欧美一级片一区| 国产美女精品| 久久九九免费视频| 美脚丝袜一区二区三区在线观看| 国产一区二区久久| 久久精品视频在线看| 噜噜噜久久亚洲精品国产品小说| 在线精品视频在线观看高清| 久久综合电影一区| 欧美成人午夜影院| 一本到12不卡视频在线dvd| 欧美经典一区二区| 亚洲每日在线| 亚洲欧美国产毛片在线| 国产一区再线| 免费视频一区二区三区在线观看| 亚洲国产成人午夜在线一区| 亚洲美女中出| 久久免费视频网| 在线观看亚洲一区| 欧美激情精品久久久六区热门| 亚洲精品中文字幕在线| 亚洲欧美综合国产精品一区| 国产在线成人| 欧美高清不卡在线| 亚洲午夜在线观看| 免费成人黄色片| 一区二区av| 国产日韩欧美在线看| 欧美大胆人体视频| 亚洲一区二区三区在线观看视频| 久久久免费精品| 亚洲理伦在线| 国产精品人成在线观看免费| 久久久综合网| 亚洲一区二区在| 嫩草影视亚洲| 欧美亚洲免费在线| 亚洲精品一区二区三区不| 国产精品网站在线播放| 鲁大师影院一区二区三区| 中日韩美女免费视频网址在线观看 | 亚洲欧美日韩人成在线播放| 1000部精品久久久久久久久| 欧美视频日韩| 免费观看久久久4p| 欧美一区二区黄色| 一区二区免费在线观看| 欧美国产三区| 久久精品91久久久久久再现| 一区二区三区欧美在线观看| 亚洲高清二区| 欧美顶级少妇做爰| 久久精品一二三| 亚洲一区三区在线观看| 亚洲欧洲综合另类| 一区二区三区在线高清| 国产日韩欧美在线视频观看| 欧美午夜国产| 欧美精品一区在线| 女人色偷偷aa久久天堂| 久久精品国产一区二区电影 | 日韩午夜av电影| 亚洲国产精品美女| 欧美高清视频在线观看| 久久综合狠狠综合久久综合88 | 91久久嫩草影院一区二区| 精久久久久久| 一色屋精品视频在线观看网站| 国产欧美一区二区精品性| 国产精品美女久久久| 国产精品久久久亚洲一区| 国产精品v欧美精品∨日韩| 欧美特黄a级高清免费大片a级| 欧美日韩视频一区二区| 国产精品福利影院| 国产免费成人av| 国产自产v一区二区三区c| 在线不卡免费欧美| 亚洲精品国产精品乱码不99| 亚洲精选久久| 一区二区三区你懂的| 亚洲欧美一区二区三区在线| 欧美一级夜夜爽| 久久久久一区二区三区四区| 欧美成人午夜激情在线| 亚洲另类在线一区| 午夜久久久久久| 久久躁日日躁aaaaxxxx| 欧美久久久久久久久久| 国产精品美女一区二区| 国产一区欧美| 日韩亚洲精品视频| 午夜精品久久久久久| 欧美在线播放| 老牛影视一区二区三区| 欧美承认网站| 在线综合视频| 午夜精品久久久久久久久久久| 久久本道综合色狠狠五月| 久久人人97超碰国产公开结果| 久久这里有精品15一区二区三区| 欧美国产日韩a欧美在线观看| 欧美日韩三级一区二区| 国产精品欧美久久| 亚洲国产精品专区久久| 99国产成+人+综合+亚洲欧美| 国产视频观看一区| 日韩视频一区二区三区| 亚洲色图自拍| 一区二区免费在线视频| 久久伊人免费视频| 亚洲国产成人午夜在线一区 | 亚洲美女av在线播放| 亚洲婷婷国产精品电影人久久| 一区二区精品国产| 欧美成人激情视频免费观看| 日韩一二三在线视频播| 久久成人18免费网站| 欧美另类专区| 国产美女在线精品免费观看| 亚洲理伦电影| 久久麻豆一区二区| 亚洲精品美女91| 久久男人av资源网站| 国产精品mm| 激情校园亚洲| 亚洲欧美精品伊人久久| 老司机午夜精品| 一区二区日韩精品| 美女被久久久|