UVa11640 Mayor Election题目链接题意输入格式输出格式样例输入样例输出分析AC 代码题目链接UVa - 11640 Mayor Election题意在宇宙的某个角落有一座城市名叫 Shohor。Shohor 的市民天性非常民主。几个月后他们将举行市长选举因此所有市长候选人都在开始竞选活动。所有候选人都想在竞选中使用海报于是他们向选举委员会EC申请允许张贴海报。经过长时间的讨论选举委员会决定候选人将被允许沿着 SAH Shoroni 路张贴海报。但是每个特定候选人能张贴的海报数量由委员会限定。所有海报都是 1 米 × 1 米大小。海报必须并排张贴因此如果某人张贴 K 张海报它们将占据道路 K 米的长度。SAH Shoroni 的总长度为 L 米。候选人们以及委员会希望利用道路的每一寸。因此沿路的海报总数始终等于道路长度。尽管每个候选人都应被允许张贴相同数量的海报但其中一些候选人非常有影响力并且设法改变了他们可以张贴的海报数量我说过他们是民主的但我从未提到他们是否腐败。对于每位候选人委员会已经决定他会被分配一个长度至少为 li、至多为 ui 的区域。但不论每位候选人被允许用海报覆盖多长所有候选人的区域长度之和等于道路总长度。选举委员会办公室位于道路的一端。因此道路上的任何位置都可以用其距办公室的距离来描述。每位候选人将被分配一个区间 [ai, bi]以便他可以在该区间内张贴自己的海报。对于所有候选人这些区间互不重叠并且完全覆盖整条道路。所有候选人都有若干种不同的海报。如果人们一遍又一遍地看到相同的海报他们会感到无聊因此他们决定对于任何一张海报 pi它最多可以连续出现 ci 次。任意两位候选人不会有相同的海报显然你不会指望有人为对手竞选吧。Shohor 的市民知道道路的长度。他们也知道EC 将允许第 i 位候选人至少张贴 ai 张海报至多张贴 bi 张海报。区域的分配将据此进行也就是说离选举委员会办公室最近的海报属于候选人 1接下来的区域属于候选人 2依此类推。请帮助 Shohor 的市民计算他们将会看到多少种不同的海报序列。输入格式第一行输入包含一个整数 TT ≤ 3表示测试用例的数量。接下来是 T 个测试用例每个测试用例前面有一个空行。每个测试用例以一个整数 NN ≤ 50开头表示市长候选人的数量。接下来是 N 行每行描述一位候选人。每位候选人的描述以三个整数开头PiPi ≤ 10、li 和 ui0 ≤ li ≤ ui ≤ 2000分别表示不同海报的数量、他被允许张贴的最少海报数和最多海报数。随后是 Pi 个整数 cj1 ≤ cj ≤ 10表示第 j 张海报最多可以连续出现的次数。之后是一个整数 QQ ≤ 100000表示需要处理的查询数量。接下来的 Q 行每行包含一个整数 L1 ≤ L ≤ 100000表示道路长度。输出格式对于每个查询输出用海报完全覆盖道路的方案数。答案可能非常大因此所有答案对 786433 取模。具体格式请参考样例输入输出。每个测试用例后输出一个空行。样例输入1 2 2 1 4 2 2 1 1 5 3 9 1 2 3 4 5 6 7 8 9样例输出Case #1: Query 1: 0 Query 2: 2 Query 3: 6 Query 4: 12 Query 5: 20 Query 6: 16 Query 7: 10 Query 8: 0 Query 9: 0分析充分理解题意后可知本题分两阶段求解即可1、用dp求出每个候选人i ii张贴x xx张海报的方案数c ( i , x ) c(i,x)c(i,x)2、FFT 计算多项式乘法∏ i 1 n [ c ( i , l i ) ∗ x l i c ( i , l i 1 ) ∗ x l i 1 ⋯ c ( i , u i ) ∗ x u i ] \displaystyle \prod_{i1}^{n}[c(i,l_i)*x^{l_i}c(i,l_i1)*x^{l_i1}\cdotsc(i,u_i)*x^{u_i}]i1∏n[c(i,li)∗xlic(i,li1)∗xli1⋯c(i,ui)∗xui]各项系数。说一下 dp 的状态设计计 d[n][k] 表示总共放了 n 张海报且最后的海报是第 k 种且最后的这张海报连续数量为 1 的方案数那么状态转移方程为d [ n ] [ k ] ∑ i 1 , i ! k p ( d [ n − c i ] [ i ] d [ n − c i 1 ] [ i ] ⋯ d [ n − 1 ] [ i ] ) \displaystyle d[n][k]\sum_{i1,i!k}^{p} (d[n-c_i][i]d[n-c_i1][i]\cdotsd[n-1][i])d[n][k]i1,i!k∑p(d[n−ci][i]d[n−ci1][i]⋯d[n−1][i])。AC 代码#includeiostream#includecstring#includecmathusingnamespacestd;#defineM786433#defineL100001#defineT117#defineX2010#defineN50#defineP11intd[X][P],c[P],n,totT;structcomplex{doublex,y;voidoperator(constcomplext){xt.x;yt.y;}complexoperator-(constcomplext)const{return{x-t.x,y-t.y};}complexoperator*(constcomplext)const{return{x*t.x-y*t.y,x*t.yy*t.x};}}s[N][T];voidfft(complex(a)[T],intinv){for(inti0,j0;itot;i){if(ji){complex ta[i];a[i]a[j];a[j]t;}intktot;while(j(k1))j~k;j|k;}for(intstep1;steptot;step1){doublealphainv*M_PI/step;for(intk0;kstep;k){complex wk{cos(alpha*k),sin(alpha*k)};for(intEkk;Ektot;Ekstep1){intOkEkstep;complex twk*a[Ok];a[Ok]a[Ek]-t;a[Ek]t;}}}}voidsolve(){cinn;for(inti0;in;i){intp,l,u;cinplu;memset(d,0,sizeof(d));for(intj0;jp;j)cinc[j],d[1][j]1;for(intj2;ju;j)for(intk0;kp;k){for(intx0;xp;x)if(x!k)for(intt1;tc[x]tj;t)d[j][k](d[j][k]d[j-t][x])%M;}for(intj0;jl;j)s[i][j]{0.,0.};for(intjl;ju;j){intfj1?1:0;for(intx0;xp;x)for(intt1;tc[x]tj;t)f(fd[j-t1][x])%M;s[i][j]{1.*f,0.};}for(intju1;jtot;j)s[i][j]{0.,0.};}for(inti1;in;i){fft(s[0],1);fft(s[i],1);for(intj0;jtot;j)s[0][j]s[0][j]*s[i][j];fft(s[0],-1);for(intj0;jtot;j)if(jL){longlongfs[0][j].x/tot.5;s[0][j]{1.*(f%M),0.};}elses[0][j]{0.,0.};}intq;cinq;for(inti1;iq;i){intx;cinx;coutQuery i: int(s[0][x].x)endl;}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intt;cint;for(inti1;it;i){coutCase #i:endl;solve();coutendl;}return0;}
