UVA 13149

uva13149.cpp

/*
給你一個Binary String長度 < 10^5
定義成長操作為在兩兩間隔間插入 其XOR值
查詢在經過 g < 10^4 成長後 區間內0,1的數量mod prime

思路

首先查詢區間[a,b]可以以[0,b]-[0,a-1]來計算所以問題可以精簡成為單向成長

那麼在一次成長過程中0增加的數量為相同的鄰居 1則反之

所以我只要能算出在每次成長後相同和相異的數量就可以知道0,1的數量

所以列舉可能存在的關係

00 -> 000 (同0會產生2x同0)
11 -> 101 (同1會產生2x異)
10 -> 110 (異會產生1x異 1x同1)

接下來因為他的查詢區間並不是直接給index而是成長路徑與開始index

成長路徑為D,R構成

1 1
  |D
101

1 1
 \R
101

所以在 10010 從 1 開始的RDD會是
10010
1       0       0       1       0
          \R
1   1   0   0   0   1   1   1   0
            |D
1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 1 0
            |D
110110110000000001101101110110110
            ^

D的話就是照前面的方式維護就可

但是R的話需要目前結尾與下一個才可以知道是什麼資料

所以需要維護結尾和下一個的值 (endval,nextval)

在D的時候 nextval = endval^nextval

在R的時候 endval  = endval^nextval

然後記得在R的時候維護異同關係的數量

*/
#include <cstdio>
#include <tuple>
#include <cstring>
#include <iostream>
using namespace std;
const long long prime=342307123;
char str[100010];
bool dat[100010];
int g;
char gf[10010],gt[10010];
int gpf,gpt;

tuple<long long,long long,bool> getcount(const char *path , int idx){
    long long diff=0,zsame=0,osame=0,one=0,zero=0;
    bool endval=dat[idx];
    bool nextval=dat[idx+1];
    for(int i = 0 ; i <= idx ; i ++){
        if(dat[i])one++;
        else zero++;
    }
    for(int i = 1 ;i <= idx ;i ++){
        if(dat[i-1]==dat[i]&&!dat[i])zsame++;
        else if(dat[i-1]==dat[i]&&dat[i])osame++;
        else diff++;
    }
    for(int i = 0 ; i < g-1 ; i ++){
        long long ndiff=diff+2*osame;
        long long nzsame=2*zsame;
        long long nosame=diff;
        zero+=osame+zsame;
        one+=diff;
        diff=ndiff%prime;
        zsame=nzsame%prime;
        osame=nosame%prime;
        if(path[i]=='R'){
            endval=endval^nextval;
            if(endval)one++;
            else zero++;
            if((endval^nextval)==endval&&endval)osame++;
            else if((endval^nextval)==endval&&!endval)zsame++;
            else diff++;
        }
        else {
            nextval=endval^nextval;
        }
        one%=prime;
        zero%=prime;
    }
    zero%=prime;
    one%=prime;
    return make_tuple(zero,one,endval);
}

int main (){
    int T;
    scanf("%d",&T);
    for(int I = 1 ; I <= T ; I ++){
        scanf("%s%d",str,&g);
        scanf("%d",&gpf);
        if(g>1)scanf("%s",gf);
        scanf("%d",&gpt);
        if(g>1)scanf("%s",gt);
        int len = strlen(str);
        for(int i = 0 ; i < len ; i ++){
            if(str[i]=='1')dat[i]=true;
            else dat[i]=false;
        }
        long long tone,tzero,tendval;
        long long fone,fzero,fendval;
        tie(fzero,fone,fendval) = getcount(gf,gpf);
        tie(tzero,tone,tendval) = getcount(gt,gpt);
        long long one=tone-fone,zero=tzero-fzero;
        if(fendval)one++;
        else zero++;
        zero%=prime;
        one%=prime;
        if(zero<0)zero+=prime;
        if(one<0)one+=prime;
        cout << "Case " << I << ": " << zero << " " << one << endl;
    }
}