站外题，难度绿/蓝，求调/给个思路也行

JXR_Kalcium @ 2024-11-27 19:45:25

by JXR_Kalcium @ 2024-11-27 19:45:54

My Code.

#include <bits/stdc++.h>
#define ll long long
#define endl putchar(10)
#define spc putchar(32)
#define R register
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " = " << x, endl
#endif

inline ll read()
{
    ll x=0,f=1; char c=getchar();

    while(c<48 || c>57)
    {
        if(c=='-') f=-1;
        c=getchar();
    }

    while(c>47 && c<58)
    x=(x<<1)+(x<<3)+c-48, c=getchar();
    return x*f;
}

inline void write(ll x)
{
    static ll sta[41]; ll top=0;
    if(x<0) putchar('-'), x=-x;
    do sta[top++]=x%10, x/=10; while(x);
    while(top) putchar(sta[--top]+48);
}

ll n,l[501],r[501],x[1001],len[1001],f[501][1001],cnt,c,sum,ans;
const ll mod=998244353;
unordered_map<ll,ll> bz;

void qsort(ll x[], ll l, ll r)
{
    if(l>r) return;
    ll i=l, j=r, p=x[l];

    while(i!=j)
    {
        while(x[j]>=p && i<j) --j;
        while(x[i]<=p && i<j) ++i;
        if(i<j) swap(x[i],x[j]);
    }

    swap(x[i],x[l]);
    qsort(x,l,i-1); qsort(x,i+1,r);
}

void exgcd(ll a, ll b, ll &x, ll &y)
{
    if(!b) {x=1; y=0; return;}
    exgcd(b,a%b,y,x); y-=a/b*x;
}

ll inv(ll a, ll b)
{
    ll x,y; exgcd(a,b,x,y);
    return (x+b)%b;
}

int main()
{
    #ifdef ONLINE_JUDGE
    freopen("array.in","r",stdin);
    freopen("array.out","w",stdout);
    #endif

    n=read();

    for(R int i=1; i<=n; ++i)
    {
        l[i]=read(); r[i]=read();
        if(!bz[l[i]]) bz[l[i]]=1, x[++cnt]=l[i];
        if(!bz[r[i]]) bz[r[i]]=1, x[++cnt]=r[i];
    }

    qsort(x,1,cnt);
    for(R int i=1; i<cnt; ++i)
    len[i]=x[i+1]-x[i]+1, f[1][i]=1;

    for(R int i=2; i<=n; ++i)
    {
        for(R int j=1; j<cnt; ++j)
        {
            c=1;

            for(R int k=i-1; k; --k)
            {
                sum=0;
                for(R int p=j; p<cnt; ++p) sum=(sum+f[k][p])%mod;
                c=c*(len[j]+i-k)%mod*inv(i-k,mod)%mod;
                f[i][j]=(f[i][j]+sum*c%mod)%mod;
            }
        }
    }

    for(R int i=1; i<n<<1; ++i)
    ans=(ans+f[n][i])%mod; write(ans);
    return 0;
}

by JXR_Kalcium @ 2024-11-27 19:48:23

TJ 中的思路.

本题考察了 DP，组合数学的相关知识。

30pts

我们用计数 dp。

设 dp_{i,j} 表示前 i 个数，最后一个数是 j 的合法方案数，转移：dp_{i,j} = \sum_{k \geq j} dp_{i-1,k}。

+30pts

考虑 l_i=l_j，r_i=r_j，假设 A=r_i-l_i+1，问题相当于求解值域 [1,A] 的不增序列，可以直接利用组合数插板法分析出答案。

80pts

上面两档分启发我们同时从 DP 和组合的角度考虑问题。

用每个 L_i, R_i 做分界点，把所有的数分组。

设离散化的数组为 re，则第 i 组的数包括 [re_i, re_{i+1})。

这样我们可以愉快地 dp 了，设 dp_{i,j} 表示前 i 个数，最后一个数在第 j 组的合法方案数。通过枚举 k，表示 a_{k+1,···,i} 全在第 j 组，进行转移：

100pts

这个内层求和显然可以用前缀和优化，所以总时间复杂度为 O(n^3)。

by _fairytale_ @ 2024-11-27 19:51:21

@JXR_Kalcium

原题 P3643 [APIO2016] 划艇

by JXR_Kalcium @ 2024-11-27 19:53:42

@fairytale 谢谢已关，但是题目本质不太一样