[APIO2016]划艇

在首尔城中，汉江横贯东西。在汉江的北岸，从西向东星星点点地分布着 $aia_iai 至 bib_ibi 之间任意选择（ai≤bi）。$

值得注意的是，编号为

输入所有学校的 $ai,bia_i, b_iai,bi 的值，求出参加庆典的划艇有多少种可能的情况，必须有至少一艘划艇参加庆典。两种情况不同当且仅当有参加庆典的某种颜色的划艇数量不同。$

题解　

　　31分算法

　　设f[i][j]表示第i个学校派j（a[i]<=j<+b[i]）个划艇，且i以后的学校都不派划艇(为了保证不重不漏，想一下就知道了)，那么f[i][j]就等于$sum limits_{l=1}^{i-1}sumlimits_{r=1}^{j-1}f[l][r]+1$

　　这就相当于在以l为最后一个派划艇的学校后在加一个学校i，原来f[l][r]仍属于总答案的一部分，+1是只有i选择派出的情况

　　枚举i,j,l,r,复杂度O(n^4)，观察上面的柿子，可以用树状数组（有人用的是线段树）维护前缀和，那么省去l,r

两层循环，只要在当前树状数组中找到1~j-1 前缀和，就是f[i][j],再加到树状数组中就可以了，因此f[][]可以省略。

　　注意要倒着枚举j,以免正着枚举f[i][j-1]加进数组后影响f[i][j]，当然也可以用数组先记录一下，等当前层i的j枚举一遍之后在插入

　　不要忘了离散化a[i]~b[i];

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
map<long long, int> p1, p2;
int n, num, a[510], b[510], sum[210000000], p[12200000], s[1000000];
int lowbit(int x) { return x & (-x); }
void add(int x, int d) {
    while (x <= num) {
        sum[x] = (sum[x] + d) % mod;
        x += lowbit(x);
    }
}
int ask(int x) {
    int ans = 0;
    while (x) {
        ans = (ans + sum[x]) % mod;
        x -= lowbit(x);
    }
    return ans % mod;
}
int main() {
    //    freopen("boat.in","r",stdin);
    //    freopen("boat.out","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);
        for (int j = a[i]; j <= b[i]; j++) {
            if (p1[j] == 0)
                p1[j] = 1, s[++s[0]] = j;
        }
    }
    sort(s + 1, s + s[0] + 1);
    for (int i = 1; i <= s[0]; i++) p2[s[i]] = ++num;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = p2[a[i]], b[i] = p2[b[i]];
        for (int j = b[i]; j >=a[i] ; j--) {
            int w= ask(j - 1) % mod;
            ans = (ans + w+ 1) % mod;
            add(j, w + 1);
        }
    }
    printf("%lld
", ans % mod);
}

31分代码

　　100分算法

　　上面的思路，即使离散化也会超时，因为它枚举的j是a[i]~b[i],那么考虑一下可不可以只枚举a[i],b[i].

显然是可以的，将a[i],b[i]+1存进s[]，离散化后为了不重不漏设j-1~j区间长度s[j]-s[j-1],左闭右开（建议不太清楚的朋友们手模一下）

　　设f[i][j]表示最后一个派出划艇的学校是i，派出了j-1~j个中的一个数的总方案数

　　方案分两部分：

　　1. i从j-1~j选一个，前面所有的学校要么不选要么从1～j-1区间中选，方案数 $sumlimits_{l=1}^{i-1}sumlimits_{r=1}^{j-1} f[l][r]*C_{len}^1$

　　2.i从j-1~j选一个，前面有学校也从j-1~j中选，定第一个从j-1~j中选的学校为k，显然总方案数为（k~i%&^%*的一堆方案数）* $sumlimits_{l=1}^{k-1}sumlimits_{r=1}^{j-1} f[l][r]$

　　首先1.和2.中 $sumlimits_{l=1}^{i-1}sumlimits_{r=1}^{j-1} f[l][r]$ $sumlimits_{l=1}^{k-1}sumlimits_{r=1}^{j-1} f[l][r]$ 可以用二维前缀和表示

　　然后就是求2.柿子前面那一堆了

　　可知k~i学校一定选择j-1~j中的数或者选择0,因为k和i都从j区间中选，k+1~i-1学校可以选择j区间的如果选的话一定从j区间中选，如果不选就选0，而不可以选j区间的一定不能派划艇

　　先另起一个话题

　　　　从长度为len（元素各不相同）的区间中选择n个数，使满足数列严格递增

　　　　答案很明显 $C_{len}^n$

　　　　有3个长度为3（元素各不相同）的相同区间，每个区间可以选一个数也可以不选，使选出来的数严格递增

　　　　选0个区间方案数$C_3^0*C_3^0$

　　　　选1个区间 $C_3^1*C_3^1$

　　　　选2个区间 $C_3^2*C_3^2$

　　　　选3个区间 $C_3^3*C_3^3$

　　　　方案总数 $C_3^0*C_3^0+C_3^1*C_3^1+C_3^2*C_3^2+C_3^3*C_3^3$

　　　　由$C_n^m=C_n^{n-m}$可知，以上式子可以换成 $C_3^3*C_3^0+C_3^2*C_3^1+C_3^1*C_3^2+C_3^0*C_3^3$

　　　　这是一个从3+3个人里选3个人的问题，前三人中选3人那后三人中只能选0人$cdots$以次类推，方案数为$C_6^3$

　　言归正转，设[k,i]区间中可以选j区间的个数为p, j区间长度为len,则问题转化成有p个相同的长度为len的区间，可以选可以不选，使选出的数严格递增

另外，为了避免不重不漏，k和i必选，这个后面再做解释，式子为：

　　　　　　　　$C_{p-2}^0*C_{len}^2+C_{p-2}^1*C_{len}^{3}+C_{p-2}^2*C_{len}^4+cdots+C_{p-2}^{p-2}*C_{len}^p$

　　同样可以看出方案数 $C_{l+p-2}^{p}$,定义来求一定会TLE，由于l过大也不能用杨辉三角，所以用到了$C_{n+1}^{m+1}=C_n^m*frac{n+1}{m+1}$ 递推

　　说到不重不漏，i必选是肯定的（f[i][j]就是这么定义的%￥%￥……），k如果不一定选，当k+1作为第一个选j区间的学校，此时k一定不选，这就与k作为第一个而k不选，k+1有可能选有重复

　　p表示[k,i]之间可选j区间的学校个数，倒序枚举k，同时记录p(遇到满足条件的就p++),同时由p递推组合数,注意p一开始为1，k==i-1是p==2……

　　二维前缀和f[i][j]，表示1～i学校从1~j区间选的方案总数

　　　　　　　$f[i][j]=len*f[i-1][j-1]+sumlimits_{k=i-1}^{1} C_{l+p-2}^p*f[k-1][j-1] $

　　f[n][m]即为最终答案（二维前缀和嘛）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int mod = 1e9 + 7;
map<long long, int> p1, p2;
int n, num;
long long a[510], b[510],s[1010], f[510][1010],inv[510],l[1010];
int main() {
    scanf("%d", &n);
    inv[1]=1;
    for(int i=2;i<=500;i++){
        inv[i]=(long long)((mod-mod/i)*inv[mod%i])%mod;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &a[i], &b[i]);
        if (p1.count(a[i])==0)
            p1[a[i]] = 1, s[++s[0]] = a[i];
        if (p1.count(b[i]+1)==0)
            p1[b[i]+1] = 1, s[++s[0]] = b[i]+1;
    }
    sort(s + 1, s + s[0] + 1);
    for (int i = 1; i <= s[0]; i++){
        p2[s[i]] = ++num;
        l[num]=s[i]-s[i-1];
    }
    for (int i = 1; i <= n; i++) a[i] = p2[a[i]]+1, b[i] = p2[b[i]+1];
    for(int i=0;i<=num;i++) f[0][i]=1;
    for (int i = 1; i <= n; i++) {
        f[i][0]=1;
        for (int j = a[i]; j <=b[i]; j++) {
            f[i][j]=(long long)f[i-1][j-1]*l[j]%mod;
            int now=1,c=l[j]-1;
            for (int k=i-1; k; k--) {
                if(a[k]<=j&&b[k]>=j){
                    now++;
                    c=((((long long)c*(l[j]+now-2))%mod)*inv[now])%mod;
                    if(!c) break;
                    f[i][j]=((long long)f[i][j]+(long long)c*f[k - 1][j - 1])%mod;
                }
            }
        }
        for(int j=1;j<=num;j++){
            f[i][j]=(((long long)f[i][j]+f[i][j-1]+f[i-1][j]-f[i-1][j-1])%mod+mod)%mod;
        }
    }
    printf("%lld", (f[n][num]-1+mod)%mod);
}

$Will$ $Be$ $The$ $King$

[APIO2016]划艇

题目描述