题目链接

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 的市民计算他们将会看到多少种不同的海报序列。

输入格式

第一行输入包含一个整数 T（T ≤ 3），表示测试用例的数量。接下来是 T 个测试用例，每个测试用例前面有一个空行。
每个测试用例以一个整数 N（N ≤ 50）开头，表示市长候选人的数量。
接下来是 N 行，每行描述一位候选人。每位候选人的描述以三个整数开头：Pi（Pi ≤ 10）、li 和 ui（0 ≤ li ≤ ui ≤ 2000），分别表示不同海报的数量、他被允许张贴的最少海报数和最多海报数。随后是 Pi 个整数 cj（1 ≤ cj ≤ 10），表示第 j 张海报最多可以连续出现的次数。
之后是一个整数 Q（Q ≤ 100000），表示需要处理的查询数量。
接下来的 Q 行，每行包含一个整数 L（1 ≤ 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_{i=1}^{n}[c(i,l_i)*x^{l_i}+c(i,l_i+1)*x^{l_i+1}+\cdots+c(i,u_i)*x^{u_i}]i=1∏n​[c(i,li​)∗xli​+c(i,li​+1)∗xli​+1+⋯+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_{i=1,i!=k}^{p} (d[n-c_i][i]+d[n-c_i+1][i]+\cdots+d[n-1][i])d[n][k]=i=1,i!=k∑p​(d[n−ci​][i]+d[n−ci​+1][i]+⋯+d[n−1][i])。

AC 代码

#include<iostream>#include<cstring>#include<cmath>usingnamespacestd;#defineM786433#defineL100001#defineT1<<17#defineX2010#defineN50#defineP11intd[X][P],c[P],n,tot=T;structcomplex{doublex,y;voidoperator+=(constcomplex&t){x+=t.x;y+=t.y;}complexoperator-(constcomplex&t)const{return{x-t.x,y-t.y};}complexoperator*(constcomplex&t)const{return{x*t.x-y*t.y,x*t.y+y*t.x};}}s[N][T];voidfft(complex(&a)[T],intinv){for(inti=0,j=0;i<tot;++i){if(j>i){complex t=a[i];a[i]=a[j];a[j]=t;}intk=tot;while(j&(k>>=1))j&=~k;j|=k;}for(intstep=1;step<tot;step<<=1){doublealpha=inv*M_PI/step;for(intk=0;k<step;k++){complex wk={cos(alpha*k),sin(alpha*k)};for(intEk=k;Ek<tot;Ek+=step<<1){intOk=Ek+step;complex t=wk*a[Ok];a[Ok]=a[Ek]-t;a[Ek]+=t;}}}}voidsolve(){cin>>n;for(inti=0;i<n;++i){intp,l,u;cin>>p>>l>>u;memset(d,0,sizeof(d));for(intj=0;j<p;++j)cin>>c[j],d[1][j]=1;for(intj=2;j<=u;++j)for(intk=0;k<p;++k){for(intx=0;x<p;++x)if(x!=k)for(intt=1;t<=c[x]&&t<j;++t)d[j][k]=(d[j][k]+d[j-t][x])%M;}for(intj=0;j<l;++j)s[i][j]={0.,0.};for(intj=l;j<=u;++j){intf=j<1?1:0;for(intx=0;x<p;++x)for(intt=1;t<=c[x]&&t<=j;++t)f=(f+d[j-t+1][x])%M;s[i][j]={1.*f,0.};}for(intj=u+1;j<tot;++j)s[i][j]={0.,0.};}for(inti=1;i<n;++i){fft(s[0],1);fft(s[i],1);for(intj=0;j<tot;++j)s[0][j]=s[0][j]*s[i][j];fft(s[0],-1);for(intj=0;j<tot;++j)if(j<L){longlongf=s[0][j].x/tot+.5;s[0][j]={1.*(f%M),0.};}elses[0][j]={0.,0.};}intq;cin>>q;for(inti=1;i<=q;++i){intx;cin>>x;cout<<"Query "<<i<<": "<<int(s[0][x].x)<<endl;}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intt;cin>>t;for(inti=1;i<=t;++i){cout<<"Case #"<<i<<':'<<endl;solve();cout<<endl;}return0;}