POI2007完结撒花~

 

首先将n转化为四进制，从低位到高位DP

f[i]表示这一位不向下一位借位

g[i]表示这一位向下一位借位，但借的那个不算在i

f[0]=0,g[0]=inf

f[i]=merge(f[i-1]+b[i],g[i-1]+b[i]+1)

g[i]=merge(f[i-1]+4-b[i],g[i-1]+3-b[i])

 

#include
     
      #include
      
       #define N 1670struct E{  int x,y;  E(){}  E(int _x,int _y){x=_x,y=_y;}  inline E operator+(int _x){return E(x+_x,y);}  inline E operator+(E b){return x==b.x?E(x,(y+b.y)%1000000000):(x
       
        >=2;    for(b[++n]=a[0]/10;l&&!a[l];l--);  }  for(f[0]=E(0,1),g[0]=E(N,0),n++,i=1;i<=n;i++)f[i]=(f[i-1]+b[i])+(g[i-1]+(b[i]+1)),g[i]=(f[i-1]+(4-b[i]))+(g[i-1]+(3-b[i]));  return printf("%d",f[n].y),0;}