數(shù)學與程序設計

1、JSOI 2009.數(shù)學與程序設計數(shù)學與程序設計JSOI 2009.引例 問題描述問題描述有一個自然數(shù)有一個自然數(shù)n，在他的首尾兩，在他的首尾兩端添上一個端添上一個1，由于，由于1是自然數(shù)之首，便形是自然數(shù)之首，便形成一個成一個“兩頭蛇數(shù)兩頭蛇數(shù)”1N1。如果。如果“兩頭蛇兩頭蛇”數(shù)數(shù)1N1正好是原自然數(shù)正好是原自然數(shù)N的的k倍，問倍，問n是多少？是多少？ 現(xiàn)在請你編程解決?，F(xiàn)在請你編程解決。JSOI 2009.兩頭蛇數(shù)100110.1.101000.1.10100.11.knNnkNnkNnkJSOI 2009.程序設計中的數(shù)學 數(shù)論 組合數(shù)學 母函數(shù) 計算幾何 JSOI 2009.程序設計

2、中的數(shù)學 基本數(shù)論 組合數(shù)學 計算幾何 容斥原理 母函數(shù) JSOI 2009.初等數(shù)論 整除 同余 素數(shù)JSOI 2009.指數(shù)取余 輸入整數(shù)輸入整數(shù)m,n,k，求，求mn mod k的值。其中的值。其中m,n,k為為自然數(shù)（自然數(shù)（m,n在長整形范圍內，在長整形范圍內，k=46340）。）。ab (mod m)cd (mod m)acbd(mod m)次數(shù)壓縮？次數(shù)壓縮？同余同余 窮舉窮舉 (m mod k)n xkxxxn.321JSOI 2009.389 mod 7 89=64+16+8+1 313 (mod 7) 3232 (mod 7)2 (mod 7) 34(32)2 (mod 7

3、)22 (mod 7)4 38(34)2 (mod 7)42 (mod 7)2 316(38)2 (mod 7)22 (mod 7)4 332(316)2 (mod 7)42 (mod 7)2 364(332)2 (mod 7)22 (mod 7)4 389(364)(316)(38)(31) (mod 7) 5 (mod 7) JSOI 2009.質多項式 給定多項式 f(x)=an*xn an-1*xn-1 . a0*x0，如果an0 ,我們稱f(x)是一個n次多項式。 類似自然數(shù)里質數(shù)的概念，也可以給出“質多項式”概念。給定多項式f(x)，如果找不到次數(shù)至少為1的多項式g(x)和h(x)

4、滿足f(x)=g(x) * h(x)，我們稱f(x)為質多項式 。 為了簡化起見，我們規(guī)定多項式的系數(shù)只能取兩個數(shù)：0或1。并且重新定義在0,1上的加法和乘法如下： 0+00 0+11 1+01 1+10 0*00 0*10 1*00 1*11 如：(x2+x1)(x1+1)=x3+x2+x2+x1=x3+x1 對于給定的正整數(shù)k，求出次數(shù)為k的質多項式。 如：輸入 1 輸出 x+1 輸入 5 輸出 x5+x2+1 JSOI 2009.質多項式解題思路 尋找質數(shù) + 窮舉 窮舉k次的多項式，檢驗能否被已經找到的質多項式整除，若不能則本身也是質多項式。 多項式除法 * 0+00 0+11 1+0

5、1 1+10 0*00 0*10 1*00 1*11 加法：XOR 乘法：正常 減法：XOR 除法：正常JSOI 2009.x3+x 、 x+1 、 x2+xJSOI 2009.程序設計中的數(shù)學 基本數(shù)論 組合數(shù)學 計算幾何 容斥原理 母函數(shù) JSOI 2009.平行四邊形的個數(shù)平行四邊形的個數(shù) 把三角形把三角形ABC的三邊各的三邊各n等分，過各等分點作等分，過各等分點作各邊的平行線，將三角形各邊的平行線，將三角形ABC分割成一些小平分割成一些小平行四邊形，計算這些小平行四邊形的個數(shù)。行四邊形，計算這些小平行四邊形的個數(shù)。JSOI 2009.就一類平行四邊形進行討論41nC31nC42nCJS

6、OI 2009.方程的解方程的解 已知方程 x1+x2+x3+xm=n 其中x1=a1,x2=a2,xm=am 且miian1 求方程的非負整數(shù)解的組數(shù) 令x1= x1-a1, x2=x2-a2, xm= xm-am x1 + x2 + xm= P11mmpCJSOI 2009.程序設計中的數(shù)學 基本數(shù)論 組合數(shù)學 計算幾何 容斥原理 母函數(shù) JSOI 2009.蜂族的旅行 和其他昆蟲不同，為了不至于迷路，蜜蜂在蜂巢（緊密連接的正六邊形）中行走必須遵守一定的路線。把一個正方形的中心看作原點。如果一只蜜蜂要從A(x1,y1)點飛到B(x2,y2)點，且AB不在同一六邊形的話，那么它必須按照蜂族的

7、飛行規(guī)則，首先飛到包含A點的正六邊形的中心，然后每次都只能從一個正六邊形的中心飛到和它相鄰的六邊形中心，直到它飛到包含B點的正六邊形的中心為止，然后再飛往B點。 知道正六邊形的邊長d與A、B點的坐標，算出蜜蜂的飛行距離。（A、B都不會剛好落在某個六邊形的邊上）。 樣例1.0 -3.2 2.2 3.3 07.737JSOI 2009.蜂族的旅行 A、B在同一六邊形，直接計算直線距離 如何判斷兩點在同一正六邊形？JSOI 2009.)3,0(kd pdypdx2323)233,23(pdkdpdJSOI 2009.12p3dy32233213232),(或或pdykdxdxpyx確定所在的六邊形并

8、計算到頂點的距離從AB經過的六邊形個數(shù)JSOI 2009.程序設計中的數(shù)學 基本數(shù)論 組合數(shù)學 計算幾何 容斥原理 母函數(shù) JSOI 2009.小蟲問題 在一個7*7的方格中，每個小方格內都有一條小蟲，約定在同一個時刻方格中的小蟲必須向周圍（上下左右4個方向）爬一格。 證明：在爬了一格之后，至少有一個小方格是空的。JSOI 2009.被繪壞的玉米地 “哈姆，外星人又在那了！”。埃塞和哈姆他們的玉米地是長方形的。每年在豐收之前，他們的玉米地都會很奇怪的遭到毀壞(據(jù)埃塞說是外星人干的)。所有破壞的地方都是以 1 米為半徑的圓米為半徑的圓。哈姆發(fā)現(xiàn)，如果玉米地上建立一個適當?shù)闹苯亲鴺讼档脑?，那些圓心

9、的坐標將都為整數(shù)圓心的坐標將都為整數(shù)。萬幸的是，埃塞和哈姆有玉米保險，但必須把損壞的面積統(tǒng)計出來。JSOI 2009.JSOI 2009.程序設計中的數(shù)學 基本數(shù)論 組合數(shù)學 計算幾何 容斥原理 母函數(shù) JSOI 2009.質數(shù)分解問題 任何大于 1 的自然數(shù) n，都可以寫成若干個大于等于 2 ，且小于等于 n 的質數(shù)之和表達式(包括只有一個數(shù)構成的和表達式的情況)，并且可能有不止一種質數(shù)和的形式。例如9 的質數(shù)和表達式就有四種本質不同的形式： 9 = 2+2+5 = 2+2+2+3 = 3+3+3 = 2+7 。 自然數(shù) n (2n200)可以寫成多少種本質不同的質數(shù)和表達式。 JSOI 2009.母函數(shù) 給定數(shù)列a0,a1,an,構造一函數(shù) F(x)=a0f0(x)+a1f1(x)+anfn(x)+ 稱F(x)為數(shù)列a0,a1,an,的母函數(shù)， 序列f0(x),f1(x),fn(x),稱為標志函數(shù)。 F(x)=a0 x0+a1x1+anxn+ JSOI 2009.普通型母函數(shù) 設從n元集合S=a0,a1,an中取個元素的組合為bk，若限定元素ai出現(xiàn)的次數(shù)不超過mi，則該組合數(shù)系列的母函數(shù)為：nimmmix10JSOI 2009.砝碼稱重 有重量為1，3，5克的砝碼各兩個，問 （1）可以稱出多少種不同重量的物品？ （2）若要稱出重量為7克的物品，所使用的砝碼有多少種