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

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>
            国产精品爱久久久久久久| 欧美高清免费| 国产欧美欧美| 久久精品72免费观看| 性8sex亚洲区入口| 黑丝一区二区| 欧美黄污视频| 欧美日韩一区二区视频在线| 亚洲一区二区三区中文字幕在线| 亚洲视频在线看| 黄色精品免费| 亚洲精品欧美| 国产日韩欧美综合| 欧美激情一区二区三区在线视频| 欧美日韩国产成人在线| 欧美一区二区网站| 美女性感视频久久久| 亚洲一区二区精品在线| 欧美一区二区日韩| 日韩视频一区二区| 香蕉精品999视频一区二区| 亚洲二区在线| 在线视频日韩精品| 亚洲国产精品免费| 亚洲欧美在线磁力| 日韩午夜激情电影| 午夜视频久久久| 亚洲精品永久免费| 午夜日韩福利| 亚洲图片欧洲图片日韩av| 欧美在线免费观看| 在线亚洲国产精品网站| 久久久久在线| 欧美在线资源| 欧美亚洲第一页| 欧美国产日韩精品免费观看| 国产精品夜夜夜一区二区三区尤| 欧美成人有码| 国语自产精品视频在线看8查询8| 99国产精品久久久久久久| 在线免费观看一区二区三区| 亚洲欧美一区二区精品久久久| 一区二区成人精品 | 欧美freesex交免费视频| 国产精品欧美一区喷水| 亚洲精选视频在线| 亚洲精品乱码久久久久久日本蜜臀| 欧美一区二区三区四区高清| 亚洲香蕉网站| 欧美激情综合在线| 你懂的网址国产 欧美| 国产真实久久| 午夜欧美视频| 亚洲欧美视频在线观看| 欧美色偷偷大香| 亚洲人体一区| 亚洲精品小视频| 欧美不卡激情三级在线观看| 老司机凹凸av亚洲导航| 精东粉嫩av免费一区二区三区| 亚洲欧美亚洲| 久久免费午夜影院| 国内精品久久久久久久影视蜜臀| 亚洲欧美第一页| 亚洲欧美中文在线视频| 国产精品一区二区男女羞羞无遮挡| 亚洲免费av片| 亚洲欧美大片| 国产欧美日韩视频| 久久国产精品亚洲va麻豆| 狼狼综合久久久久综合网| 在线不卡中文字幕| 欧美成人一区二区三区| 亚洲精品日韩综合观看成人91| 99综合在线| 欧美性色视频在线| 亚洲主播在线| 麻豆freexxxx性91精品| 亚洲国产精品小视频| 欧美激情中文字幕乱码免费| 亚洲美女精品久久| 亚洲欧美制服另类日韩| 国产视频亚洲精品| 久久综合九色综合久99| 亚洲欧洲中文日韩久久av乱码| 日韩视频免费在线| 国产欧美日韩综合| 久热精品视频在线观看一区| 亚洲激情午夜| 欧美一级播放| 亚洲国产裸拍裸体视频在线观看乱了 | 亚洲欧美在线一区二区| 国产一区欧美| 欧美精品色一区二区三区| 中文亚洲视频在线| 久久婷婷人人澡人人喊人人爽| 亚洲精品欧美一区二区三区| 国产精品久久看| 久久免费偷拍视频| 99精品99| 欧美96在线丨欧| 亚洲男女毛片无遮挡| 亚洲国产欧美在线人成| 国产精品高精视频免费| 麻豆成人小视频| 亚洲欧美激情一区二区| 亚洲国产精品传媒在线观看| 久久国产精品久久w女人spa| 99v久久综合狠狠综合久久| 国产午夜精品久久| 欧美四级伦理在线| 女人色偷偷aa久久天堂| 欧美亚洲尤物久久| 99国产麻豆精品| 欧美大片免费观看在线观看网站推荐 | 看片网站欧美日韩| 亚洲欧美国产一区二区三区| 亚洲精品欧美| 久久免费黄色| 久久成人av少妇免费| 亚洲午夜精品久久| 亚洲精品激情| 亚洲激情在线观看| 激情综合电影网| 国产区二精品视| 国产精品久久精品日日| 欧美欧美在线| 欧美激情中文字幕在线| 免费久久99精品国产自| 久久精品123| 欧美中文字幕第一页| 亚洲欧美日韩国产综合精品二区| 一区二区三区高清在线| 日韩午夜在线| 日韩视频永久免费观看| 亚洲日本va午夜在线影院| 亚洲黄色影院| 亚洲国产精品成人精品| 亚洲高清不卡一区| 亚洲第一精品久久忘忧草社区| 免费欧美在线| 欧美黄色免费| 91久久视频| 亚洲美女在线国产| 亚洲婷婷综合久久一本伊一区| 99天天综合性| 亚洲嫩草精品久久| 午夜一级在线看亚洲| 欧美一区二区视频网站| 久久精品中文| 麻豆精品传媒视频| 欧美精品激情在线观看| 欧美日韩精品在线播放| 国产精品高潮呻吟久久av无限| 国产精品免费一区二区三区在线观看 | 亚洲美女中文字幕| 夜久久久久久| 亚洲欧美中文在线视频| 欧美一区二区三区啪啪| 老司机一区二区三区| 欧美激情欧美狂野欧美精品| 欧美日韩免费区域视频在线观看| 国产精品家庭影院| 国产日韩欧美一二三区| 激情欧美日韩一区| 亚洲美女中文字幕| 午夜影院日韩| 六十路精品视频| 亚洲精品视频免费在线观看| 一本色道**综合亚洲精品蜜桃冫| 午夜精品久久久99热福利| 久久视频一区| 欧美视频在线免费| 国色天香一区二区| 99视频精品全部免费在线| 久久精品91| 亚洲精品中文字幕有码专区| 欧美一区二区视频网站| 欧美人与性禽动交情品| 国产伊人精品| 中文久久乱码一区二区| 欧美在线高清视频| 亚洲韩国青草视频| 欧美一区二区在线免费观看 | 亚洲欧美大片| 欧美激情视频网站| 国产中文一区二区| 一区二区三区毛片| 免费久久久一本精品久久区| 一区二区欧美精品| 亚洲综合国产| 亚洲成色精品| 久久激情视频久久| 欧美性久久久| 日韩午夜三级在线| 你懂的国产精品永久在线| 午夜精品一区二区三区在线视| 欧美日韩精品免费观看视频| 在线成人av网站| 久久精品一区二区三区不卡|