题目：

先说说自己的想法吧。

设f[ i ][ j ]表示当前在倒数第 i 个位置，当前和后面的最高的列(最大的数)是 j 的方案数。

考虑当前填0，则用f[ i-1][ j ]转移；当前填1，相当于把后面的都消去最底下一行，用f[ i-1 ][ j-1 ]转移。

所以f[ i ][ j ]=∑(k:0~j)f[ i-1 ][ k ]。然后矩阵优化。

结果发现 j 的范围达到1e9，也就是要建1e9*1e9的矩阵。于是萎了。

看TJ：

关键的思路可能在于发现随便选即可，之后排序。

没错，不用 +i 转换成升序也是可以这样转化的。很经典。

C( )里必须判断 if(n<m)return 0; ！因为n%mod,m%mod时很容易传进n<m的参数！

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;const int mod=1e6+3;int T,n,m,l,r,jc[mod+5],jcn[mod+5];int pw(int x,int k){  int ret=1;while(k){
   if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;}void init(){  jc[0]=1;  for(int i=1;i
        
         =0;i--)jcn[i]=(ll)jcn[i+1]*(i+1)%mod;}int C(int n,int m){  if(n