NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2012高中組初賽
 pD. 長長的蚯蚓天天長長

作者 主題: pD. 長長的蚯蚓天天長長  (閱讀 3015 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
pD. 長長的蚯蚓天天長長
« 於: 十一月 24, 2012, 10:32:04 pm »

測資範圍:N、S<=107、M<=50

解題方法:DP。用一個陣列 P[] 記錄達到每一個長度的機率,
已知 P[0]=1, 而 P[k]=(P[k-1]+P[k-2]+...+P[k-M+1]+P[k-M])/M,
但是 k<M 或 k>N 時上下限要修正, 時間複雜度 O(N*M)。

程式碼等官方測資出來之後再補。
« 上次編輯: 十一月 25, 2012, 12:51:41 am 由 sagit »
記錄

c2251393

  • 新手
  • *
  • 文章數: 1
    • 檢視個人資料
Re: pD. 長長的蚯蚓天天長長
« 回覆 #1 於: 十一月 25, 2012, 12:27:53 am »

這題還有一個T會到514
所以這樣( O(T*S*M) )會TLE(我傳過
會AC的解好像是利用矩陣乘法快速冪
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
Re: pD. 長長的蚯蚓天天長長
« 回覆 #2 於: 十一月 25, 2012, 11:39:25 am »

感謝指正, 補充一下矩陣乘法的做法,
在 M=4 的情況下, 假設有一個 4X4 的矩陣 A:
1/m 1 0 0
1/m 0 1 0
1/m 0 0 1
1/m 0 0 0
當 x=0 時 A[y][ x]=p, 當 x=y+1 時 A[y][ x]=1, 其他則為 0。
再設另一個 1X4 的矩陣B:
1
0
0
0
由上而下代表 p[0]、p[1]、p[2]、p[3],
AxB 之後則會變成 p[1]、p[2]、p[3]、p[4],
故將 B 乘上 N 次的 A 則會得到 p[n]、p[n+1]、p[n+2]、p[n+3],
雖然這樣的做法時間複雜度為 O(N*M2),
但可以先用快速冪的技巧算出 A 的 N 次方,
http://www.csie.ntnu.edu.tw/~u91029/DivideAndConquer.html#a4
這樣時間複雜度則會降為 O(lgN*M2),
就算再乘上 T 也會過了。
« 上次編輯: 十一月 25, 2012, 11:41:58 am 由 sagit »
記錄

xavier13540

  • 新手
  • *
  • 文章數: 7
    • 檢視個人資料
Re: pD. 長長的蚯蚓天天長長
« 回覆 #3 於: 十一月 26, 2012, 06:15:19 pm »

雖然這樣的做法時間複雜度為 O(N*M2),
但可以先用快速冪的技巧算出 A 的 N 次方,
http://www.csie.ntnu.edu.tw/~u91029/DivideAndConquer.html#a4
這樣時間複雜度則會降為 O(lgN*M2),
就算再乘上 T 也會過了。
請問一下為什麼時間複雜度是 O(lgN*M2) 呢?矩陣乘法時間複雜度不是 O(M3) 嗎?
« 上次編輯: 十一月 26, 2012, 07:03:04 pm 由 xavier13540 »
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
Re: pD. 長長的蚯蚓天天長長
« 回覆 #4 於: 十一月 26, 2012, 08:42:06 pm »

請問一下為什麼時間複雜度是 O(lgN*M2) 呢?矩陣乘法時間複雜度不是 O(M3) 嗎?

你說的對, 不過這題的重點在於從 O(N) 變成 O(lgN),
那個 M 最大只有50, 影響其實不大。
記錄

traveler

  • 新手
  • *
  • 文章數: 1
    • 檢視個人資料
Re: pD. 長長的蚯蚓天天長長
« 回覆 #5 於: 十一月 26, 2012, 11:29:24 pm »

事實上,因為後面的機率是前面幾個取平均,所以會趨於定值。
加上小數點本來就有誤差,所以當N大ㄧ點時可以當作定值來算。
這樣答案的約略值可以用N,M,S的公式表示,
無論N,S多大都可以(還會越來越精確)。
« 上次編輯: 十一月 27, 2012, 09:58:54 pm 由 traveler »
記錄

rockwyc992

  • 新手
  • *
  • 文章數: 4
    • 檢視個人資料
Re: pD. 長長的蚯蚓天天長長
« 回覆 #6 於: 十一月 28, 2012, 09:47:54 am »

我們班有人用O(1)就可以轉移狀態可是還是TLE

算起來運算量跟矩陣一樣耶(好像只多一點點)


//剛剛試了一下發現其實N>1000以後連double都無法表現出他們的差距了

N>100時就小於題目要求的精確度了= ="

所以其實只要先算出N<100的就好了
記錄

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
Re: pD. 長長的蚯蚓天天長長
« 回覆 #7 於: 十一月 14, 2013, 09:23:18 am »

補程式碼:
代碼: [選擇]
#include <cstdio>
#include <algorithm>

using namespace std;

int m;
struct Matrix { double p[50][50]; };
Matrix Mul(const Matrix &a, const Matrix &b)
{
    Matrix c;
    int x, y, z;
    for (y=0; y<m; y++)
        for (x=0; x<m; x++)
            for (z=0, c.p[y][x]=0; z<m; z++)
                c.p[y][x]+=a.p[y][z]*b.p[z][x];
    return c;
}

int main()
{
    int t, n, s, x, y, bit;
    double ans;
    Matrix a, b;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d", &n, &m, &s);
        if (s<=n)
        {
            puts("100.0%");
            continue;
        }
        if (s>=n+m)
        {
            puts("0.0%");
            continue;
        }
        for (y=0; y<m; y++)
            for (x=0; x<m; x++)
            {
                a.p[y][x] = ( x==y ? 1.0 : 0.0 );
                if (x==0) b.p[y][x]=1.0/m;
                else if (x==y+1) b.p[y][x]=1.0;
                else b.p[y][x]=0.0;
            }
        for (bit=1; bit<=n; bit<<=1)
        {
            if (n&bit) a=Mul(a, b);
            b=Mul(b, b);
        }
        for (y=s-n, ans=0.0; y<m; y++) ans+=a.p[y][0];
        printf("%.1lf%%\n", ans*100);
    }
    return 0;
}
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2012高中組初賽
 pD. 長長的蚯蚓天天長長