zcmimi's blog
查看原题

点击跳转

https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370149

题意:

给一个序列A,要求支持以下操作:

  1. 区间乘

  2. 区间里所有数都变成自己的k次幂

  3. 求区间乘积(mod 10000000007)

由于模数是质数,所以可以将每个数都变成原根的次幂

这样区间乘转化为区间加,区间次幂转化为区间乘,求区间乘积转化为求区间和

#include<bits/stdc++.h>
const int N=100011,p=1000000007,P=p-1,G=5;
int rd(){int x=0;char c;bool f=0;for(c=getchar();c<'0'||'9'<c;c=getchar())f^=c=='-';for(x=c-48,c=getchar();'0'<=c&&c<='9';x=x*10+c-48,c=getchar());return f?-x:x;}
int n,q,s[N<<2],add[N<<2],mul[N<<2];
int v[]={0,0,381838282,884237698,763676564,1,266075974,936544532,145514840,768475390,381838283,649233168,647914256,144547565,318382808,884237699,527353122,895459693,150313666,701153241,763676565,820782224,31071444,82047235,29752532,2,526385847,652713082,700221090,347375814,266075975,198670980,909191404,533470860,277297969,936544533,532151948,289190395,82991517,28785257,145514841,802264261,202620500,24616936,412909726,768475391,463885517,730741137,411590814,873089058,381838284,779697385,908224129,616590335,34551358,649233169,82059366,585390933,729214096,178404868,647914257,234516540,580509262,705019916,291029680,144547566,915309142,351358075,659136251,966284933,318382809,557546595,913990230,559624399,671028677,884237700,464829799,585777694,410623539,414776906,527353123,536950774,184102537,809672376,584458782,895459694,406455218,231613506,794748008,689565125,150313667,81092091,845723799,82908672,112579413,701153242,793429096,993378125,254927334,417708552,763676566,495914368,161535661,991051336,290062405,820782225,998428617,326036185,416389640,525353314,31071445,173428087,463897648,429750477,967229215,82047236,111052372,913022955,560243150,832004219,29752533,298466330,616354822,686501953,962347544,3,86858192,155622902,672867962,908854634,526385848,26958408,297147418,637697767,733196357,652713083,40974527,540374100,348123209,293399235,700221091,614978829,939384877,793780733,295828506,347375815,941462681,757326750,52866953,109607515,266075976,468364065,846668081,663935077,967615976,198670981,792461821,967234449,796615188,500828027,909191405,18591761,918789056,238291131,565940819,533470861,191510652,98758628,966297064,289095130,277297970,469628625,788293500,328851128,613451788,936544534,176586284,62642560,71403401,492996069,532151949,546888614,462930373,118754232,227562075,289190396,464746954,544692855,494417695,589257608,82991518,366164793,175267372,23539458,375216401,28785258,636765616,829772542,799546834,912024915,145514842,235595767,877752650,283920340,543373943,802264262,372889612,850522625,671900687,350386403,202620501,437098732,380266893,441784287,707874467,24616937,798227922,135215506,907191596,443862091,412909727,40007252,555266369,768794522,845735930,768475392,811588759,342799273,349067491,566661897,463885518,470015386,492890654,924677391,294861231,730741138,942081432,299014598,213842495,732754158,411590815,733768720,680304612,421188466,998193104,873089059,68340229,845700806,344185820,693910068,381838285,241119035,468696474,731280403,537461184,779697386,54706238,17661842,290692910,225734921,908224130,115851198,408796690,872301485,678985700,616590336,19536043,573802817,115034633,298959763,34551359,462560014,422812809,965329789,922212382,649233170,729961491,31035300,675237517,967146370,82059367,345578910,996817111,82704431,321223153,585390934,175619009,738808787,677666788,790919380,729214097,877615817,323300957,912101836,139165026,178404869,434705235,301946244,491445797,226594800,647914258,961161468,850202347,380152060,228506357,234516541,45773353,235180417,349454252,875289028,580509263,800796434,174300097,489302579,349072725,705019917,178453464,145590444,882666309,996608982,291029681,210273877,400430043,596612928,300627332,144547567,620129413,409591006,947779101,667285663,915309143,602268191,573348934,57665779,480596910,351358076,348135340,319223134,670933412,313988169,659136252,847904148,851466907,809633584,170131776,966284934,710689410,312731484,995290070,329982019,318382810,797260647,558424566,533507235,444480842,557546596,453241683,716241911,874834351,366249874,913990231,402306476,928726896,182704022,844768655,559624400,500592514,368582295,609400357,570739645,671028678,553134861,846585236,624185975,926531137,884237701,876255977,491923379,971095890,18654643,464829800,39860594,748003075,970055489,557105654,585777695,405377740,793092326,757054683,720569060,410623540,977506928,18603892,911196106,211610818,414776907,181385110,648104085,293863191,521935459,527353124,574882870,617434049,343218545,259590926,536950775,665758622,938423563,925212225,324474452,184102538,424611792,754727894,114949394,232360901,809672377,53738963,177636927,732224685,247548773,584458783,485092561,818937014,499216521,762105175,895459695,823622569,171061066,89712743,678018425,406455219,22572234,180066198,946054688,517053788,231613507,289029872,783200476,825700373,340871020,794748009,641564442,421845534,129669796,937104651,689565126,150632798,993845213,227574206,977541982,150313668,451497423,193427035,352601757,724637555,81092092,730905773,761838722,948500179,548172769,845723800,475803029,851853668,919505556,874728936,82908673,306515667,410804030,676699513,287902601,112579414,851472141,323919708,673850104,680852880,701153243,595680777,385065719,114592434,146327964,793429097,433737960,115606996,902829459,62142888,993378126,803026748,727424537,380031380,122528823,254927335,687842587,450178511,242835501,227539082,417708553,726024102,494091121,75748344,615613462,763676567,982996326,622957317,192803239,850534756,495914369,113118679,173332822,919299466,734145295,161535662,496168925,436544520,353866317,399500124,991051337,672531192,379974299,607573203,213088820,290062406,486914916,497689480,636072233,790634972,820782226,254139761,94130667,60823976,164094470,998428618,946880258,401374325,946811826,955641099,326036186,496872915,377233761,680798045,522322220,416389641,794831137,844398296,431126306,804651091,525353315,347168065,659991722,304050658,2991924,31071446,48529049,111799767,351321432,412873582,173428088,57075793,377246546,348984646,169164501,463897649,428930547,727417192,427073348,378655387,429750478,464542713,473495300,703061435,835310771,967229216,678916854,557457291,250402485,120647063,82047237,59505064,298408322,172757656,907777156,111052373,746216902,259454093,265823497,705139239,913022956,293940112,195024716,521003308,899824221,560243151,714010234,816543517,708296745,683784526,832004220,873284079,796262607,608433082,696897442,29752534,748641546,342999744,119833459,232040623,298466331,761990342,986766785,610344639,168158032,616354823,875288702,427611635,307293942,617018699,686501954,731292534,368755462,257127304,314280758,962347545,734760317,182634710,626109651,556138379,4,871140861,234624095,730911007,184650082,86858193,385696585,560291746,321336424,527428726,155622903,264504585,17636617,378447258,326021979,672867963,81412879,592112159,158329748,782268325,908854635,978451210,614024899,682465614,827638036,526385849,19453198,1967689,443555346,791429288,26958409,329617377,328099783,49123939,342531174,297147419,491028875,984106473,924244950,955187216,637697768,439504061,429423049,862435192,653032214,733196358,883749708,729973622,247787358,701061416,652713084,52771688,936414888,695826451,929922651,40974528,227036965,229742424,656202916,233305183,540374101,191471860,450899589,551970058,761137900,348123210,957940143,92527686,354253078,694569766,293399236,377128346,697723948,711820301,808915083,700221092,421457424,179098923,990343636,940262848,614978830,915345517,432458894,826319124,696576885,939384878,183252290,835079965,280718215,98080187,793780734,256672627,616991850,748088156,544104739,295828507,927595862,784144758,618006412,310565172,347375816,564542304,978569639,226606931,305426158,941462682,920076629,882430796,921332824,750420577,757326751,991238639,591237,952577927,114605847,52866954,729938498,934973143,695101199,228423512,109607516,6024251,578147760,308369413,262580711,266075977,709275566,258094253,125356727,873761661,468364066,352934166,539586166,400492925,615518095,846668082,319462292,421698876,461897840,129841351,663935078,351893765,322952433,938943936,518957057,967615977,901899540,787216022,791579360,174930602,198670982,138892959,109972613,102407336,503417496,792461822,206779757,359345204,88890,400442174,967234450,293034382,270431985,593449100,756539177,796615189,366295003,563223392,379064105,29942361,500828028,675701473,941189873,903773741,626200824,909191406,458040509,956721152,208857561,999272331,18591762,725056827,183197455,641429208,378740433,918789057,171504504,47596898,346797706,320261839,238291132,307050501,725770177,706312734,849567481,565940820,607079689,806450074,891734457,136566170,533470862,496787676,689646277,614199183,613043530,191510653,915272998,435577245,768548745,559475209,98758629,114062961,851384062,629387055,164451860,966297065,694751628,866930843,229816602,200775290,289095131,881054803,235010856,143943451,966942129,277297971,371237630,205460845,516096998,552899348,469628626,471551025,241952849,59856701,239248300,788293501,623046479,404410516,937618645,561904480,328851129,327892964,675157072,898892070,64010068,613451789,495905640,670868154,761853509,165038752,936544535,207538649,403193844,722709302,796339528,176586285,903509641,23402718,991122233,803683816,62642561,511508078,310672493,318942927,92167428,71403402,186183936,532471080,431894372,375683489,492996070,609412488,110832492,359380258,546046794,532151950,512050022,833335705,845399160,575265317,546888615,734440039,668881664,106475831,264389752,462930374,700685266,112744049,458905538,143676998,118754233,330338455,963502940,930011051,492514271,227562076,119418109,857641311,702094160,233691944,289190397,301343832,759526720,256567212,798432364,464746955,574242293,688353949,685034126,792642312,544692856,58537789,889171523,669740883,373540271,494417696,630233002,233310417,884311496,705757990,589257609,55688380,964453890,62691156,704171964,82991519,29828136,977519059,772408781,766904001,366164794,496430716,880846674,528166246,476918626,175267373,397341960,815576242,94511569,497445278,23539459,284667735,815035131,443981170,480850620,375216402,962094621,184865024,229943761,109262813,28785259,761869662,545661558,504367105,338798287,636765617,293828698,69680863,331110272,832016793,829772543,624673783,551523355,609377364,106664171,799546835,728364560,107862378,486505883,875929403,912024916,457586626,65098646,997451744,941903477,145514843,730325259,364834602,73864555,4795593,235595768,574641521,317743570,232373032,990413208,877752651,203460826,494956961};
#define ls rt<<1
#define rs rt<<1|1
void mod(int&x){if(x>=P)x-=P;}
void Mul(int&x,int y){x=1ll*x*y%P;}
void pu(int rt){mod(s[rt]=s[ls]+s[rs]);}
void build(int l,int r,int rt){
    add[rt]=0,mul[rt]=1;
    if(l==r){
        s[rt]=v[rd()];
        return;
    }
    int m=l+r>>1;
    build(l,m,ls),build(m+1,r,rs);
    pu(rt);
}
void pd(int rt,int ln,int rn){
    if(mul[rt]^1){
        Mul(s[ls],mul[rt]);
        Mul(s[rs],mul[rt]);
        Mul(mul[ls],mul[rt]);
        Mul(mul[rs],mul[rt]);
        Mul(add[ls],mul[rt]);
        Mul(add[rs],mul[rt]);
        mul[rt]=1;
    }
    if(add[rt]){
        mod(s[ls]+=1ll*add[rt]*ln%P);
        mod(s[rs]+=1ll*add[rt]*rn%P);
        mod(add[ls]+=add[rt]);
        mod(add[rs]+=add[rt]);
        add[rt]=0;
    }
}
void updm(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R){
        Mul(s[rt],v),Mul(mul[rt],v),Mul(add[rt],v);
        return;
    }
    int m=l+r>>1;
    pd(rt,m-l+1,r-m);
    if(L<=m)updm(L,R,v,l,m,ls);
    if(R>m)updm(L,R,v,m+1,r,rs);
    pu(rt);
}
void upda(int L,int R,int v,int l,int r,int rt){
    if(L<=l&&r<=R){
        mod(s[rt]+=1ll*v*(r-l+1)%P),mod(add[rt]+=v);
        return;
    }
    int m=l+r>>1;
    pd(rt,m-l+1,r-m);
    if(L<=m)upda(L,R,v,l,m,ls);
    if(R>m)upda(L,R,v,m+1,r,rs);
    pu(rt);
}
int ask(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R)return s[rt];
    int m=l+r>>1,ans=0;
    pd(rt,m-l+1,r-m);
    if(L<=m)ans=ask(L,R,l,m,ls);
    if(R>m)mod(ans+=ask(L,R,m+1,r,rs));
    return ans;
}
int pw(int x,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%p;
        b>>=1,x=1ll*x*x%p;
    }
    return res;
}
void solve(){
    n=rd(),q=rd();
    build(1,n,1);
    while(q--){
        int opt=rd(),l=rd(),r=rd();
        if(opt==1)upda(l,r,v[rd()],1,n,1);
        else if(opt==2)updm(l,r,rd(),1,n,1);
        else printf("%lld\n",pw(G,ask(l,r,1,n,1)));
    }
}
int main(){for(int T=rd();T--;)solve();}
ZOJ 3998 Yet Another Data Structure Problem
comment评论
Search
search