题解 P4684 【[IOI2008] Fish 鱼】

· · 题解

一道经典的组合计数题，当时在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;
}