青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

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 1 000 000 007.

Limits

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

Small dataset

1 ≤ mn ≤ 1000

Large dataset

1 ≤ mn ≤ 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多,能過。

賽后學(xué)習(xí)了下,也不算太難。
本來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];
  }
}


大家注意看,內(nèi)循環(huán)其實(shí)是一個(gè)區(qū)間求和。那么對于這種求和,線段樹只可以做到NlogN的。
記得以前寫過一道題的解題報(bào)告,是類似的。
pku1769 點(diǎn)樹解決塊查詢點(diǎn)操作

下面是代碼:(solve2函數(shù)是一個(gè)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, 
0sizeof(st));
    sort(S, S 
+ n);
    map
<intint> mm;
    
int i, j = 0, ans = 0;
    
for(i = 0; i < n; ++i) {
        
if(!mm.count(S[i])) {
            mm[S[i]] 
= ++j;
        }
    }
    ins(
01);
    
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;
}

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲欧美在线另类| 一本久道久久综合中文字幕| 久久久综合精品| 亚洲国产精品欧美一二99| 日韩一区二区电影网| 欧美亚日韩国产aⅴ精品中极品| 亚洲影院污污.| 蜜桃伊人久久| 亚洲视频电影在线| 激情文学综合丁香| 欧美噜噜久久久xxx| 亚洲欧美另类国产| 欧美顶级少妇做爰| 亚洲欧美国产精品va在线观看| 国产一区91精品张津瑜| 欧美激情一区二区三区四区| 亚洲无线一线二线三线区别av| 国产精品美女www爽爽爽视频| 久久精品成人一区二区三区蜜臀 | 欧美中文字幕精品| 91久久精品一区| 国产伦精品一区二区三区照片91| 久久综合九色综合欧美就去吻| 99在线观看免费视频精品观看| 久久久久国产精品一区| 一区二区三区日韩| 在线观看日韩一区| 国产精品欧美日韩| 欧美国产第一页| 久久gogo国模裸体人体| 99v久久综合狠狠综合久久| 久热精品视频在线观看一区| 亚洲私人影院在线观看| 亚洲国产精品成人| 国产日韩视频| 欧美日韩精品一区二区三区四区| 久久9热精品视频| 亚洲午夜精品视频| 亚洲精品激情| 欧美高清不卡| 久久这里只有| 欧美在线免费观看视频| 一区二区三区欧美亚洲| 亚洲娇小video精品| 海角社区69精品视频| 国产精品萝li| 欧美日韩亚洲一区二区三区在线 | 亚洲视频一二区| 亚洲毛片在线看| 亚洲国产日韩精品| 黑丝一区二区三区| 国产午夜精品一区理论片飘花| 欧美视频网站| 欧美日韩国产色综合一二三四 | 亚洲午夜精品国产| 亚洲免费观看高清在线观看 | 亚洲精品中文字幕在线| 亚洲电影成人| 欧美国产日韩xxxxx| 噜噜噜久久亚洲精品国产品小说| 欧美在线免费观看| 欧美一区二区三区四区在线观看 | 久久综合九色九九| 久久久一二三| 久久综合久久综合这里只有精品| 欧美一区二区三区日韩| 欧美一区二区三区久久精品茉莉花| 亚洲午夜精品| 亚洲欧美另类久久久精品2019| 亚洲字幕一区二区| 西瓜成人精品人成网站| 香蕉尹人综合在线观看| 欧美一区二区三区在线观看视频| 欧美一区二区三区电影在线观看| 久久都是精品| 久久久久久久999| 麻豆av福利av久久av| 欧美国产1区2区| 欧美特黄视频| 国产欧美精品一区| 怡红院精品视频在线观看极品| 在线观看日韩av先锋影音电影院| 亚洲国产精品女人久久久| 最新中文字幕亚洲| 亚洲图色在线| 欧美在线观看网站| 免费h精品视频在线播放| 欧美激情自拍| 在线一区视频| 久久不射电影网| 欧美电影资源| 国产精品久久久久久一区二区三区| 国产精品自拍在线| 一区二区在线视频| 一本色道久久综合亚洲精品高清 | 国产精品久久久久免费a∨大胸| 国产精品视频精品视频| 极品中文字幕一区| 99精品国产在热久久婷婷| 午夜精品视频在线| 欧美成人精品一区二区| 欧美一区二区三区在线观看视频| 久久久久久久久一区二区| 欧美激情精品| 亚洲一区二区成人在线观看| 久久免费99精品久久久久久| 欧美日韩国产高清视频| 国产一区二区三区高清播放| 亚洲伦伦在线| 久久九九精品99国产精品| 亚洲高清中文字幕| 午夜一区在线| 欧美日韩一区不卡| 在线成人国产| 午夜精品久久久久久99热| 欧美高清视频在线播放| 亚洲视频图片小说| 久久综合久久综合久久综合| 国产精品99一区二区| 亚洲国产经典视频| 欧美亚洲综合另类| 亚洲激情在线视频| 久久久久久精| 国产精品一区久久| 中日韩视频在线观看| 久久亚洲影音av资源网| 亚洲视频专区在线| 欧美精品在线一区| 在线播放亚洲一区| 久久不射2019中文字幕| 亚洲精品美女在线| 蜜臀av一级做a爰片久久| 国产综合av| 欧美专区福利在线| 亚洲香蕉成视频在线观看| 欧美精品在线免费播放| 亚洲国产毛片完整版| 久久久久久久久伊人| 亚洲欧美一区二区原创| 欧美视频中文一区二区三区在线观看 | 欧美插天视频在线播放| 狠狠综合久久| 久久国产主播精品| 亚洲欧美国产一区二区三区| 欧美日韩一区二区在线视频| 最新国产成人在线观看| 欧美成人一区二区三区在线观看| 欧美一区二区三区免费观看 | 好看的日韩视频| 亚洲欧美日韩国产成人精品影院| 亚洲理伦在线| 欧美日韩国产小视频在线观看| 亚洲日本成人网| 亚洲成人资源| 欧美高清在线一区二区| 亚洲精品影院在线观看| 免费不卡中文字幕视频| 久久国产黑丝| 一色屋精品亚洲香蕉网站| 久久免费一区| 久久久久www| 亚洲电影在线播放| 亚洲第一视频| 欧美国产高清| 一本色道**综合亚洲精品蜜桃冫 | 在线观看亚洲一区| 欧美国产精品日韩| 欧美风情在线观看| 一区二区三区高清不卡| 在线视频欧美日韩精品| 国产精品色网| 久久人人97超碰人人澡爱香蕉| 久久久xxx| 亚洲精品影院| 亚洲无限乱码一二三四麻| 国产久一道中文一区| 久久亚洲电影| 欧美肥婆在线| 亚洲欧美中文在线视频| 欧美一区二区三区成人| 亚洲国产欧美日韩精品| 亚洲精品一区二区在线| 国产精品入口日韩视频大尺度| 久久久久久噜噜噜久久久精品| 久久另类ts人妖一区二区| 日韩午夜剧场| 亚洲男人的天堂在线| 精品动漫av| 亚洲精品一区二区三区不| 国产精品一级| 欧美国产日韩视频| 国产精品久久久久久久久搜平片 | 先锋影院在线亚洲| 亚洲区国产区| 亚洲综合三区| 最新中文字幕亚洲| 午夜精品美女自拍福到在线 | 亚洲女人av| 毛片av中文字幕一区二区| 亚洲一区二区三区午夜|