[CF930E]/[CF944G]Coins Exhibition

题目地址：

/

博客地址：

题目大意：

一个长度为\(k(k\le10^9)\)的\(01\)串，给出\(n+m(n,m\le10^5)\)个约束条件，其中\(n\)条描述区间\([l_i,r_i]\)至少有一个\(0\)，其中\(m\)条描述区间\([l_i,r_i]\)至少有一个\(1\)。求合法的\(01\)串数量。

思路：

显然直接考虑所有的\(k\)位，就算\(\mathcal O(k)\)的线性算法也会超时，因此对于所有的\(l_i-1,r_i\)以及\(0,k\)离散化以后考虑这些关键点即可。

设关键点有\(lim\)个，对所有关键点排序，\(tmp[i]\)为\(i\)离散化前对应的数。对所有关键点排序，考虑动态规划，设\(f[i][j\in\{0,1,2\}]\)表示从后往前考虑第\(i\sim lim\)个关键点。若\(j\in\{0,1\}\)，则\(f[i][j]\)表示\(tmp[i]\sim tmp[i+1]\)中含有\(j\)的方案数后缀和。若\(j=2\)，则\(f[i][j]\)表示最后一段同时有\(0\)和\(1\)的方案数。用\(min[j\in\{0,1\}][i]\)表示对应约束条件类型为\(j\)，\(i\)右侧最近的、对应左端点不在\(i\)左侧的右端点。状态转移方程如下：

• \(f[i][0]=f[i+1][0]+f[i+1][1]-f[min[1][i]][1]+f[i+1][2]\times(2^{tmp[i+1]-tmp[i]}-2)\)
• \(f[i][1]=f[i+1][1]+f[i+1][0]-f[min[0][i]][0]+f[i+1][2]\times(2^{tmp[i+1]-tmp[i]}-2)\)
• \(f[i][2]=f[i+1][0]-f[min[0][i]][0]+f[i+1][1]-f[min[1][i]][1]+f[i+1][2]\times(2^{tmp[i+1]-tmp[i]}-2)\)

最终答案为\(f[0][2]\)。

时间复杂度\(\mathcal O((n+m)(\log(n+m)+\log k))\)。其中\(\mathcal O(\log(n+m))\)为离散化复杂度，\(\mathcal O(\log k)\)为快速幂复杂度。

源代码：

#include
    
     #include
     
      #include
      
       using int64=long long;inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}constexpr int N=1e5,mod=1e9+7;std::pair
       
         p[2][N];int tmp[N*4+2],min[2][N*4+2],f[N*4+2][3];inline int power(int a,int k) {    int ret=1;    for(;k;k>>=1) {        if(k&1) ret=(int64)ret*a%mod;        a=(int64)a*a%mod;    }    return ret;}int main() {    const int k=getint(),n=getint(),m=getint();    int lim=0;    for(register int i=0;i
        
         =0;i--) {        int g[3];        g[0]=(f[i+1][0]-f[min[0][i]][0]+mod)%mod;        g[1]=(f[i+1][1]-f[min[1][i]][1]+mod)%mod;        g[2]=(int64)f[i+1][2]*((power(2,tmp[i+1]-tmp[i])-2+mod)%mod)%mod;        f[i][0]=((int64)f[i+1][0]+g[1]+g[2])%mod;        f[i][1]=((int64)f[i+1][1]+g[0]+g[2])%mod;        f[i][2]=((int64)g[0]+g[1]+g[2])%mod;    }    printf("%d\n",f[0][2]);    return 0;}