列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[sagit]

測資範圍：N、S<=10⁷、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)。

程式碼等官方測資出來之後再補。

[c2251393]

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

[sagit]

感謝指正, 補充一下矩陣乘法的做法,
在 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*M²),
但可以先用快速冪的技巧算出 A 的 N 次方,
http://www.csie.ntnu.edu.tw/~u91029/DivideAndConquer.html#a4
這樣時間複雜度則會降為 O(lgN*M²),
就算再乘上 T 也會過了。

[xavier13540]

雖然這樣的做法時間複雜度為 O(N*M²),
但可以先用快速冪的技巧算出 A 的 N 次方,
http://www.csie.ntnu.edu.tw/~u91029/DivideAndConquer.html#a4
這樣時間複雜度則會降為 O(lgN*M²),
就算再乘上 T 也會過了。

請問一下為什麼時間複雜度是 O(lgN*M²) 呢？矩陣乘法時間複雜度不是 O(M³) 嗎？

[sagit]

請問一下為什麼時間複雜度是 O(lgN*M²) 呢？矩陣乘法時間複雜度不是 O(M³) 嗎？

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

[traveler]

事實上，因為後面的機率是前面幾個取平均，所以會趨於定值。
加上小數點本來就有誤差，所以當N大ㄧ點時可以當作定值來算。
這樣答案的約略值可以用N,M,S的公式表示，
無論N,S多大都可以(還會越來越精確)。

[rockwyc992]

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

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


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

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

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

[sagit]

補程式碼：

代碼: [選擇]

#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;
}