此题不提供链接
题目描述
题解
首先看这个 f ( i ) f(i) f(i)，其实就是个卡特兰数： f ( i ) = ( 2 i i ) i + 1 f(i)=\frac{{2i\choose i}}{i+1} f(i)=i+1(i2i?)?，这是很经典的结论了。你也可以从DP入手推一下，因为最优方案必定是选 n n n 个矩形，把DP式子列出来就知道了。
然后由于答案是 max ? i = l r v 7 [ ( i + 1 ) f ( i ) ] \max_{i=l}^rv_7[(i+1)f(i)] maxi=lr?v7?[(i+1)f(i)]，发现 ( i + 1 ) (i+1) (i+1) 被消掉了，最后只剩下 max ? i = l r v 7 [ ( 2 i i ) ] = max ? i = l r v 7 [ ( 2 i ) ! ( i ! ) 2 ] \max_{i=l}^rv_7[{2i\choose i}]=\max_{i=l}^rv_7[\frac{(2i)!}{(i!)^2}] maxi=lr?v7?[(i2i?)]=maxi=lr?v7?[(i!)2(2i)!?]。
由于答案只求7的次数，并且是阶乘，所以我们可以用另一个经典的基于递归枚举的计算方法算次数：
v
7
[
(
2
n
)
!
(
n
!
)
2
]
=
∑
i
=
0
+
∞
(
?
2
n
7
i
?
?
2
?
n
7
i
?
)
v_7[\frac{(2n)!}{(n!)^2}]=\sum_{i=0}^{+\infty}(\lfloor\frac{2n}{7^i}\rfloor-2\lfloor\frac{n}{7^i}\rfloor)
v7?[(n!)2(2n)!?]=i=0∑+∞?(?7i2n???2?7in??)
这个式子告诉我们，考虑7进制下的
n
n
n 的每个后缀，若×2过后会进位则有1的贡献，答案是所有后缀的贡献和。
这显然是可以数位DP的，只需要把 l l l 和 r r r 都转成7进制数，然后讨论是否抵上界、是否抵下界、当前位是否进位进行转移即可。
代码
暴力压位高精进制转换
#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
#define END putchar('\n')
using namespace std;
const int MAXN=100005;
const ll INF=1e18;
inline ll read(){
ll x=0;bool f=1;char s=getchar();
while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
return f?x:-x;
}
int ptf[50],lpt;
inline void print(ll x,char c='\n'){
if(x<0)putchar('-'),x=-x;
ptf[lpt=1]=x%10;
while(x>9)x/=10,ptf[++lpt]=x%10;
while(lpt)putchar(ptf[lpt--]^48);
if(c>0)putchar(c);
}
inline ll lowbit(ll x){return x&-x;}
ll mi[10]={1,7,49,343,2401,16807,117649,823543,5764801,40353607};
const ll w=40353607;
struct bigint{
vector<ll>a;bigint(){}
bigint(ll x){
a.push_back(x);
while(a.back()>=w)a.push_back(a.back()/w),a[a.size()-2]%=w;
}
inline int AT(int x){
if(x/9>=(int)a.size())return 0;
return a[x/9]/mi[x%9]%7;
}
inline bigint operator+(const bigint&b)const{
bigint res=*this;
res.a.resize(max(a.size(),b.a.size()));
for(int i=0,lim=b.a.size();i<lim;i++)res.a[i]+=b.a[i];
for(int i=0,lim=res.a.size();i<lim-1;i++)
res.a[i+1]+=res.a[i]/w,res.a[i]%=w;
while(res.a.back()>=w)
res.a.push_back(res.a.back()/w),res.a[res.a.size()-2]%=w;
while(res.a.size()>1&&!res.a.back())res.a.pop_back();
return res;
}
inline bigint operator-(const bigint&b)const{
bigint res=*this;
for(int i=0,lim=b.a.size();i<lim;i++){
res.a[i]-=b.a[i];
if(res.a[i]<0)res.a[i]+=w,res.a[i+1]--;
}
for(int i=b.a.size(),lim=res.a.size();i<lim;i++)
if(res.a[i]<0)res.a[i]+=w,res.a[i+1]--;
while(res.a.size()>1&&!res.a.back())res.a.pop_back();
return res;
}
inline bigint operator*(const bigint&b)const{
bigint res;
int la=a.size(),lb=b.a.size();
res.a.resize(la+lb);
for(int i=0;i<la;i++)
for(int j=0;j<lb;j++)res.a[i+j]+=a[i]*b.a[j];
for(int i=0,lim=res.a.size();i<lim-1;i++)
res.a[i+1]+=res.a[i]/w,res.a[i]%=w;
while(res.a.back()>=w)
res.a.push_back(res.a.back()/w),res.a[res.a.size()-2]%=w;
while(res.a.size()>1&&!res.a.back())res.a.pop_back();
return res;
}
inline bigint operator/(const ll&d)const{
bigint res=*this;
for(int i=a.size()-1;i>=0;i--){
if(i>0)res.a[i-1]+=res.a[i]%d*w;
res.a[i]/=d;
}
while(res.a.size()>1&&!res.a.back())res.a.pop_back();
return res;
}
}l=bigint(0),r=bigint(0);
int n,a[MAXN],b[MAXN],dp[MAXN][2];
inline ll HS(int x,bool up,bool dm,bool e){return x<<3|(up<<2)|(dm<<1)|e;}
unordered_map<ll,int>F;
inline int dfs(int x,bool up,bool dm,bool e){
if(x<0)return e?-1e8:0;
if(!up&&!dm)return dp[x+1][e];
if(F.find(HS(x,up,dm,e))!=F.end())return F[HS(x,up,dm,e)];
int l=dm?a[x]:0,r=up?b[x]:6,res=-1e8;
for(int i=l;i<=r;i++)
for(int t=0;t<2;t++){
if(e&&i>3-t)res=max(res,dfs(x-1,up&&i==r,dm&&i==l,t)+1);
if(!e&&i<4-t)res=max(res,dfs(x-1,up&&i==r,dm&&i==l,t));
}
return F[HS(x,up,dm,e)]=res;
}
signed main()
{
freopen("dingdingcar.in","r",stdin);
freopen("dingdingcar.out","w",stdout);
char s=getchar();
while(s<'0'||s>'9')s=getchar();
while(s>='0'&&s<='9')l=l*10+bigint(s^48),s=getchar();
while(s<'0'||s>'9')s=getchar();
while(s>='0'&&s<='9')r=r*10+bigint(s^48),s=getchar();
n=max(l.a.size()*9,r.a.size()*9);
for(int i=0;i<n;i++)a[i]=l.AT(i),b[i]=r.AT(i);
dp[0][0]=0,dp[0][1]=-1e8;
for(int i=1;i<=n;i++){//其实这个预处理的DP完全没必要
dp[i][0]=dp[i][1]=-1e8;
for(int j=0;j<7;j++){
if(j<4)dp[i][0]=max(dp[i][0],dp[i-1][0]);
if(j<3)dp[i][0]=max(dp[i][0],dp[i-1][1]);
if(j>3)dp[i][1]=max(dp[i][1],dp[i-1][0]+1);
if(j>2)dp[i][1]=max(dp[i][1],dp[i-1][1]+1);
}
}
print(max(dfs(n,1,1,0),dfs(n,1,1,1)));
return 0;
}