noi.ac 405 bzoj 4403 序列统计 题解

发表于 | 阅读次数：
本文字数： 1.1k 字 | 阅读时长 ≈ 5 分钟

题意简述

noi.ac再次蒯题，实锤了…

请你求长度在 $[1,n]$ 范围内，值域在 $[l,r]$ 范围内的序列中，不下降序列有多少个。答案对 $1000003$（是质数）取膜。

多组数据，数组组数 $T\le 100$ ，每组数据 $n,l,r\le 1e9$ ，并且保证$l\le r$

思路框架

首先，在 $[l,r]$ 范围内，和在 $[1,r-l+1]$ 范围内，没有本质上的区别。
设 $m=r-l+1$，然后答案就是 $C_{n+m}^{m}-1$

具体思路

我们先求长度固定为 $k$ 的时候，有多少满足条件的序列，然后取遍 $k=1,2\cdots n$ ，求和。

求有多少固定长度非严格上升子序列

严格上升怎么做

长度为 $k$ 的时候，值域在 $[1,m]$ 内的严格上升序列的格式就是 $C_{m}^{k}$ 。因为我们只要在 $[1,m]$ 内选出来 $k$ 个数，然后把它排一下序，那就能得到一个长度为 $k$ ，值域在 $[1,m]$ 内的一个严格上升序列了。

如何转化成非严格上升

我们在选严格上升序列的时候，假设我们当前选到的数为 $x$，那么下一个位置珂以是 $x+1,x+2…m$，有 $m-x$ 种选择。而选非严格上升序列的时候，却有 $m-x+1 $种选择。

那这个时候，我们只要把 $m$ 变成 $m+1$ ，那答案就和严格上升的时候一样了！！

序列的长度为 $k$ ，那么我们在选第 $[1,k-1]$这些位置的时候，都要把 $m$ 变成 $m+1$。那一共就是变成 $m+k-1$。

总结一下，长度为 $k$ 值域在 $[1,m]$ 之间的非严格上升序列个数为 $C_{m+k-1}^{k}$

优化求和

我们要求 $\sum\limits_{i=1}^{n} C_{m+i-1}^{i}=C_{m}^1+C_{m+1}^2+C_{m+2}^3…+C_{m+n-1}^{n}$

显然，$C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}$

那也就是说，我们珂以用两个相邻的 $C_{n}^{xxx}$ 得到一个 $C_{n+1}^{xxx}$。

那么我们考虑给第一项加上一个 $C_{m}^{0}$，也就是 $1$，然后最后减掉一个 $C_{m}^{0}$。

那我们开始推式子了，系好安全带（为了方便理解，我拆开$\Sigma$）：
原式
$=C_{m}^{0}+C_{m}^{1}+C_{m+1}^{2}+C_{m+2}^3…+C_{m+n-1}^n-1$
$=C_{m+1}^{1}+C_{m+1}^{2}+C_{m+2}^3+…+C_{m+n-1}^n-1$
$=C_{m+2}^{2}+C_{m+2}^{3}+….+C_{m+n-1}^n-1$
$=C_{m+n-1}^{n-1}+C_{m+n-1}^{n}-1$
$=C_{m+n}^{n}-1$

所以答案就是 $C_{m+n}^{n}-1$。预处理阶乘（逆元）+Lucas定理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define mod 1000003
    #define N (mod<<1)
    #define int long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }

    int fac[N],ifac[N];
    //阶乘，和阶乘的逆元
    void Init()
    {
        fac[0]=1;
        F(i,1,mod-1) fac[i]=fac[i-1]*i%mod;
        ifac[mod-1]=mod-1;
       //mod是质数，那么(mod-1)! %mod=mod-1，这个是Wilson定理
       //然后mod-1的逆元，显然是mod-1
        D(i,mod-2,0) ifac[i]=ifac[i+1]*(i+1)%mod;
    }
    int n,l,r;
    void Input()
    {
        Rd(3,&n,&l,&r);
    }

    int C(int n,int m) //Lucas定理
    {
        if (m>n) return 0;
        if (n<mod and m<mod)
        {
            return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
        }
        return C(n/mod,m/mod)*C(n%mod,m%mod)%mod;
    }
    void Soviet()
    {
        int len=r-l+1; //len就是m了
        printf("%lld\n",(C(n+len,len)+mod-1)%mod);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Init();
        int t;R1(t);
        F(i,1,t)
        {
            Input();
            Soviet();
        }
    }
    #undef int //long long 
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w