欧美精品在线免费播放,国产主播在线一区,亚洲激情视频在线观看

Google Cod Jam Round1C C題 Increasing Speed Limits

Posted on 2008-08-02 15:06 oyjpart 閱讀(2641) 評論(0) 編輯收藏引用所屬分類: ACM/ICPC或其他比賽

Increasing Speed Limits

Problem

You were driving along a highway when you got caught by the road police for speeding. It turns out that they've been following you, and they were amazed by the fact that you were accelerating the whole time without using the brakes! And now you desperately need an excuse to explain that.

You've decided that it would be reasonable to say "all the speed limit signs I saw were in increasing order, that's why I've been accelerating". The police officer laughs in reply, and tells you all the signs that are placed along the segment of highway you drove, and says that's unlikely that you were so lucky just to see some part of these signs that were in increasing order.

Now you need to estimate that likelihood, or, in other words, find out how many different subsequences of the given sequence are strictly increasing. The empty subsequence does not count since that would imply you didn't look at any speed limits signs at all!

For example, (1, 2, 5) is an increasing subsequence of (1, 4, 2, 3, 5, 5), and we count it twice because there are two ways to select (1, 2, 5) from the list.

Input

The first line of input gives the number of cases, N. N test cases follow. The first line of each case contains n, m, X, Y and Z each separated by a space. n will be the length of the sequence of speed limits. m will be the length of the generating array A. The next m lines will contain the m elements of A, one integer per line (from A[0] to A[m-1]).

Using A, X, Y and Z, the following pseudocode will print the speed limit sequence in order. mod indicates the remainder operation.

for i = 0 to n-1
  print A[i mod m]
  A[i mod m] = (X * A[i mod m] + Y * (i + 1)) mod Z

Note: The way that the input is generated has nothing to do with the intended solution and exists solely to keep the size of the input files low.

Output

For each test case you should output one line containing "Case #T: S" (quotes for clarity) where T is the number of the test case and S is the number of non-empty increasing subsequences mod 1000000007.

Limits

1 ≤ N ≤ 20
1 ≤ m ≤ 100
0 ≤ X ≤ 10⁹
0 ≤ Y ≤ 10⁹
1 ≤ Z ≤ 10⁹
0 ≤ A[i] < Z

Small dataset

1 ≤ m ≤ n ≤ 1000

Large dataset

1 ≤ m ≤ n ≤ 500 000

Sample

Input	Output
`2 5 5 0 0 5 1 2 1 2 3 6 2 2 1000000000 6 1 2`	`Case #1: 15 Case #2: 13`

The sequence of speed limit signs for case 2 should be 1, 2, 0, 0, 0, 4.

沒趕上Round1A 郁悶。
Round1C Solve1和2，3的large不會做，菜。Rank好像是60多，能過。

賽后學習了下，也不算太難。
本來DP方程是這樣的
for(i = 0; i < n; ++i) {
for(j = 0; j < i; ++j) {
if(A[j] < A[i]) {
dp[i] += dp[j];
}
}
}
如果對A排序并且離散化，則變成了
for(i=0; i < n; ++i) {
for(j = 0; j < A[i]; ++j) {
dp[A[i]] += dp[j];
}
}

大家注意看，內循環其實是一個區間求和。那么對于這種求和，線段樹只可以做到NlogN的。
記得以前寫過一道題的解題報告，是類似的。
pku1769 點樹解決塊查詢點操作

下面是代碼：(solve2函數是一個n^2的DP,偶水small input用的)

// Solution by alpc12
#include <stdio.h>
#include <cassert>
#include <map>
#include <algorithm>
using namespace std;

const int M = 100;
const int N = 500010;
const int MOD = 1000000007;

typedef long long LL;

int n, m, X, Y, Z;
int A[N], S[N];
int st[1048576];
int upperbound = 524288;
int dp[N];

void generate() {
    int i;
    for(i = 0; i < n; ++i) {
        S[i] = A[i%m];
        A[i%m] = ((LL)X*A[i%m]+(LL)Y*(i+1))%Z;
    }
    for(i = 0; i < n; ++i) {
        A[i] = S[i];
    }
}

int get(int x, int y) { // 左閉右開
    x += upperbound, y += upperbound;
    int ans = 0;
    while(x + 1 < y) {
        if(x&1) { // x是右子樹
            ans = (ans + st[x]) % MOD;
            x++;
        }
        if(y&1) { // y是右子樹
            y--;
            ans = (ans + st[y]) % MOD;
        }
        x >>= 1;
        y >>= 1;
    }
    if(x < y)
        ans = (ans + st[x]) % MOD;
    return ans;
}

void ins(int x, int a) {
    x += upperbound;
    while(x > 0) {
        st[x] = (st[x] + a) % MOD;
        x >>= 1;
    }
}

void solve() {
    memset(st, 0, sizeof(st));
    sort(S, S + n);
    map<int, int> mm;
    int i, j = 0, ans = 0;
    for(i = 0; i < n; ++i) {
        if(!mm.count(S[i])) {
            mm[S[i]] = ++j;
        }
    }
    ins(0, 1);
    for(i = 0; i < n; ++i) {
        A[i] = mm[A[i]];
        int sum = get(0, A[i]);
        ans = (ans + sum) % MOD;
        ins(A[i], sum);
    }
    printf("%d\n", ans);
}

void solve2() {
    int i, j, k;
    for(i = 0; i < n; ++i) dp[i] = 1;
    for(i = 1; i < n; ++i) {
        for(j = 0; j < i; ++j) {
            if(S[j] < S[i]) {
                dp[i] += dp[j];
                dp[i] %= MOD;
            }
        }
    }
    LL sum = 0;
    for(i = 0; i < n; ++i) {
        sum += dp[i];
        sum %= MOD;
    }
    printf("%I64d\n", sum);
}

int main()
{
//    freopen("C-large.in", "r", stdin);
//    freopen("C-large.txt", "w", stdout);

    int ntc, i, j, k, tc=0;
    scanf("%d", &ntc);
    while(ntc--) {
        printf("Case #%d: ", ++tc);
        scanf("%d%d%d%d%d", &n, &m, &X, &Y, &Z);
        for(i = 0; i < m; ++i) scanf("%d", A+i);
        generate();
//        solve2();
        solve();
    }
    return 0;
}

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 多串匹配樹嚴重祝賀alpc 哈爾濱奪冠 ALPC真是好樣的！！！太棒了！！！ 2009年度騰訊創新大賽 Tencent Innovation Contest 2009 開心的一天我的電影“苑” 戀，在小A -- 記ACM國際大學生程序設計競賽 Goobye to ACM \| alpc12 @ Refugee @ Chengdu alpc12 @ Refugee @ Harbin 一點組隊感想說題~

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

oyjpArt ACM/ICPC算法程序設計空間

導航

公告

常用鏈接

留言簿(41)

隨筆分類(190)

隨筆檔案(224)

文章檔案(6)

相冊

ACM大牛們

Great Sites

My Friends

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Google Cod Jam Round1C C題 Increasing Speed Limits