自动搬运

查看原文

来自洛谷，原作者为

	wu3412790 **

搬运于2025-08-24 22:02:36，当前版本为作者最后更新于2019-03-20 08:28:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道经典的组合计数题，当时在IOI现场只有Huacheng Yu一人AC。

但实际上这题并不算特别难，一名对组合数学熟练的选手完全有能力独立解决。

题目中每条鱼有长度，和一种独特的宝石。考虑按照鱼的长度排序，注意到如果两条鱼所用有的宝石是一样的，那么长的那条鱼可能拥有的宝石组合将覆盖所有短的鱼的组合，因为短的能吃的长的都能吃。

这样一来，对每种宝石只需要考虑拥有它的"最长鱼"就可以了。考虑按“最长鱼”的长度从小到大枚举每种宝石，计算方案。为了避免重复，我们对于同一组合，希望只在其最后一次出现的时候加入它。这样一来，问题转化为，对于一类宝石，它的“最长鱼”肚子里可能吐出哪些宝石组合，并且这些宝石组合不会被后面更长的“最长鱼”拥有。注意到，如果一条"最长鱼"$a$的长度小于另一条”最长鱼"$b$的长度，那么在所有颜色的宝石中，$a$只有在$c_a$和$c_b$这两种颜色的宝石上，可能吐出$b$所不能吐出的数量，这是因为对于其它颜色的宝石，由于$b$比$a$长，$b$能吃的一定大于等于$a$能吃的条数，但$a$自己有一个$c_a$颜色的宝石，它肚子里还可以不包含颜色为$c_b$的宝石，这两种情况下，$a$的这些组合是$b$没有的。

总结一下，对于一条"最长鱼" $a$，有如下两种选择方法：

(1) 在$c_a$中选出尽量多的宝石，即吃下所有能吃的颜色为$c_a$的鱼。同时如果后面的某条"最长鱼" $b$能包含更多的$c_a$，就在 $c_b$这个颜色吃$0$条来避免被$b$碾压。对于其它的颜色，数量随意，只需要把方案数乘起来。

(2) 在$c_a$中选少于最大可能的条数，对所有长度大于a的其它最长鱼，在对应的颜色下选$0$个防止被碾压。

扫描过程中需要维护一些连续段的乘积，使用一个线段树就行。时间复杂度$O(F\log F).$

总结：对于计数题来说，“没事多排序”是亘古不变的真理。本题最重要的一步就是将所有宝石的颜色按照“最长鱼”的长度排序，一旦排好序一切都会变的非常有规律，后面发现用线段树维护方案数的方案是很自然的。

#pragma GCC optimize("O3")
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int const N=5e5+1;
struct fish{
   int len,col,pre;
   friend bool operator <(fish x, fish y){
   	return x.len<y.len;
   }
}f[N];
int n,m,p,t[N*8],h[N],last[N],w[N],q[N],now[N],v[N],ans;
void add(int pos, int l, int r, int x){
   if (l==r){ 
       t[x]=(v[pos]+1) % p;
       return;
   }
   int mid=((l+r)>>1);
   if (pos<=mid) add(pos,l,mid,x*2);
   if (pos>mid) add(pos,mid+1,r,x*2+1);
   t[x]=(t[x*2]*t[x*2+1]) % p;
}
int ask(int a, int b, int l, int r, int x){
   if (a>b) return 1;
   if (a<=l && r<=b) return t[x];
   int ans=1,mid=((l+r)>>1);
   if (a<=mid) ans=ans*ask(a,b,l,mid,x*2);
   if (b>mid) ans=ans*ask(a,b,mid+1,r,x*2+1);
   return ans % p;
}
int find(int x){
   int l=1,r=m;
   while (r-l>1){
   	int mid=((l+r)>>1);
       if (f[w[mid]].len>=x) r=mid; else l=mid+1;
   }
   if (f[w[l]].len>=x) return l;
   if (f[w[r]].len>=x) return r;
   return m+1;
}
int main(){
   ios::sync_with_stdio(false);
   cin>>n>>m>>p;
   for (int i=1;i<=n;i++)
   	cin>>f[i].len>>f[i].col;
   sort(f+1,f+n+1);
   for (int i=n;i>=1;i--){
   	if (!h[f[i].col]) h[f[i].col]=i;
   	f[i].pre=last[f[i].col];
   	last[f[i].col]=i;
   }
   m=0;
   for (int i=1;i<=n;i++)
   	if (h[f[i].col]==i) w[q[f[i].col]=++m]=i;
   for (int i=1;i<=8*m;i++)
   	t[i]=1;
   for (int i=1,j=1;i<=m;i++){
   	while (f[j].len*2<=f[w[i]].len){
   		int s=f[j].col;
   		v[q[s]]++;
           now[s]=j++;
           add(q[s],1,m,1);
   	}
   	int k,d=ask(1,i-1,1,m,1);
   	if (!now[f[w[i]].col]) k=last[f[w[i]].col]; else k=f[now[f[w[i]].col]].pre;
   	if (!k) k=m+1; else k=find(f[k].len*2);
       ans=(ans+d*ask(i+1,k-1,1,m,1)+d*(v[i] % p)) % p;
   }
   cout<<ans<<endl; 
   return 0;
}