常州day1p3-白红宇

常州day1p3

阅读量：6957 次

发布时间：2019-06-27

本文共 1292 字，大约阅读时间需要 4 分钟。

给定一个 n 行 m 列的方格，每个格子里有一个正整数 a，1 ≤ a ≤ k,k ≤ n∗m 假设你当前时刻站在 (i,j) 这个格子里，你想要移动到 (x,y)，那必须满足以下三个条件 1：i < x 2：j < y 3：第 i 行第 j 列格子里的数不等于第 x 行第 y 列格子里的数求从 (1,1) 移动到 (n,m) 的不同的方案数

对于 100% 的数据，n,m ≤ 750

容易想到f[i][j]=sigma(f[k][l]|a[k][l]!=a[i][j])

我们可以容易的统计和颜色无关的情况然后去掉颜色相同的就可以了。

于是我们对每一种颜色建立一颗权值线段树

动态开点

时间复杂度O(n^2logn)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define re register#define il inlineusing namespace std;const int N=1001,NN=8000001;const int mod=1000000007;int n,m,a[N][N],k,root[NN],lch[NN],rch[NN],cnt=0;int f[N][N],s[N][N],w[NN];il int read(){ re int hs=0;re char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)){ hs=(hs<<3)+(hs<<1)+c-'0'; c=getchar(); } return hs;}il void add(re int &i,re int l,re int r,re int p,re int v){ if(i==0) i=(++cnt); w[i]=(w[i]+v)%mod; if(l==r) return; re int mid=(l+r)/2; if(p<=mid) add(lch[i],l,mid,p,v); else add(rch[i],mid+1,r,p,v); }il int sum(re int i,re int l,re int r,re int p,re int q){ if(!i) return 0; if(l==p&&r==q) return w[i]; re int mid=(l+r)/2; if(q<=mid) return sum(lch[i],l,mid,p,q); if(mid

转载于:https://www.cnblogs.com/ExiledPoet/p/5771471.html

你可能感兴趣的文章