BZOJ4403 序列统计—Lucas你好

2018-06-17 23:03:55来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

  绝对是全网写的最详细的一篇题解(因为我弱) 

  题目:序列统计  代码难度:简单  思维难度:提高+—省选

  讲下题面:给定三个正整数N、L和R,统计长度在1到N之间,元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。

  。。。    防

  。。。    蒯

  。。。    神

  。。。    器

  好了,把我的做题思路说说。

  首先我们可以看出,L和R的具体值是没有卵用的,你只需要知道它们的差+1,记为m。同时T<=100也意味着各组询问之间应该并没有关系。

  然后我们会想到,这肯定不能一步出解(事实证明我被打脸了)。然后我们来找,对于条件(i,m),它的解是怎么来的。

  长度为i,备选数的值域(下面就叫做值数)有m个的单调不下降序列有多少个呢?

  这么一想不是很好想出来。那么我们想,如果把相同的数归入一个集合,或者叫抽屉,给它们以里面的数的代数值为编号,这个序列就可以看成一段段连续的抽屉,且它们的编号成递增。

  问题是不是可以抽象成:我有m个有编号的抽屉,要把i个相同的苹果放进去,问有多少种方法?

  此时问题已经渐渐清晰成具体模型了,但对于有些人(such as me)来说还是很玄学。于是我们再看看。

  上面那个问题下,抽屉是不动物体。现在我们把苹果当成不动物体看看:

  有i个苹果,要把它们分成至多m个区间,有多少种方法?

  这个时候千万不要想复杂了。对于这个问题,如果我们不局限于单个的i和m,而是把它们巧妙转化,整合在一起的话——

  有i个苹果,m-1个挡板。我们要在苹果中间插入挡板(也可以是最两侧),有多少种方法?

  换言之——

  有m+i-1个位子,你要在里面放m-1个挡板,有多少种放法?

  那么就是显然的组合数学!C(i+m-1,m-1)!

  那么我们知道(i,m)的答案就是C(i+m-1,m-1)。

  那么答案就是sigma(i from 1 to n)C(i+m-1,m-1);

  然而这是会T的复杂度。我们画出杨辉三角(或者根本不用画),就能发现它是在三角上的一条向左下倾斜的线。那么优化就顺(sang)理(xin)成(bing)章(kuang)了:

  在右上角加一个C(m,m),根据杨辉三角的特点,我们可以一路消掉,一直到C(N+M,M);

  因为我们之前加上了C(M,M),所以答案要减一。Ans=C(N+M,M)-1;正面肛Lucas定理。

  介绍一下Lucas定理:C(N,M)%P=Lucas(N,M,P)=C(N%P,M%P)*Lucas(N/P,M/P,P);

  逆元和阶乘预处理一下就好了。

  

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
#define MID int mid=(l+r)>>1
using namespace std;
const LL Mod = 1000003;
LL cmod[Mod],A[Mod],J[Mod],n,m;
LL gi()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL C(LL N,LL M,LL P)
{
  if(M>N)return 0ll;
  LL ans=J[N];
  ans=ans*A[J[N-M]]%P;
  ans=ans*A[J[M]]%P;
  return ans;
}
LL Lucas(LL N,LL M,LL P)
{
  if(M==0)return 1ll;
  if(N<P&&M<P)return C(N,M,P);
  LL c=C(N%P,M%P,P);  if(!c)return 0ll;
  LL L=Lucas(N/P,M/P,P);return (c*L)%P;
}
int main()
{
  int T=gi();J[0]=A[1]=J[1]=1;
  for(LL i=2;i<Mod;++i)A[i]=((Mod-Mod/i)*A[Mod%i])%Mod;
  for(LL i=2;i<Mod;++i)J[i]=(J[i-1]*i)%Mod;
  while(T--)
    {
      n=gi();m=(gi()-gi());m=-m+1;
      printf("%lld\n",(Lucas(n+m,n,Mod)-1+Mod)%Mod);
    }
  return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:中值滤波,C语言实现(开园第一篇)

下一篇:CUDA基础(1):操作流程与kernel概念