電話節(jié)
總時(shí)間限制:1000ms 內(nèi)存限制:128 MB
問題描述
α大使歷盡顛簸千辛鹦赎，終于回到了α星球辜纲，
正好趕上了α星球最盛大的節(jié)日：電話節(jié)盛霎。
α星球共有 N戶人家构挤，每戶人家都有一個(gè)威望值 a i 傲诵，
在電話節(jié)的時(shí)候凯砍，每戶人家都要給其他所有人打電話，通話時(shí)間就是兩家威望的乘積掰吕，
請(qǐng)幫忙算一下果覆，一個(gè)電話節(jié)下來，α星球總共會(huì)產(chǎn)生多少通話時(shí)間殖熟，
答案可能會(huì)很大局待，最終答案 mod 10009 即可。
輸入格式
第一行一個(gè)數(shù)字 N菱属，表示α星球共有 N 戶人家钳榨。
第二行有 N 個(gè)整數(shù)，表示α星球每戶人家的威望 a i 纽门。
輸出格式
輸出一個(gè)整數(shù)薛耻，最終答案 mod 10009 的結(jié)果。
樣例輸入
3
2 3 4
樣例輸出
52
提示
a 1 和 a 2 通話時(shí)間是 6赏陵，
a 1 和 a 3 通話時(shí)間是 8饼齿，
a 2 和 a 1 通話時(shí)間是 6饲漾，
a 2 和a 3 通話時(shí)間是12，
a 3 和 a 1 通話時(shí)間是 8缕溉，
a 3 和a 2 通話時(shí)間是12考传，
總通話時(shí)間為 6 + 8 + 6 + 12 + 8 + 12 = 52。
數(shù)據(jù)規(guī)模與約定：
對(duì)于 20%的數(shù)據(jù)证鸥，1 <= N <= 100僚楞，0 <= a i <= 100。
對(duì)于 50%的數(shù)據(jù)枉层，1 <= N <= 1000泉褐。
對(duì)于 100%的數(shù)據(jù)，1 <= N <= 10 6 鸟蜡，0 <= a i <= 1000膜赃。
題解
mod 一下暴力也能得倒大部分的分?jǐn)?shù)，剩下的還是要看正解矩欠。
sum=a[i]
(i=1~N)
ans=a[i]*(sum-a[i])
(i=1~N)
注意中間過程要mod10009财剖，還要注意過程中有減法，需要把答案轉(zhuǎn)正
ans=((ans%mo)+mo)%mo
