C. Sum of Log（数位dp）

C. Sum of Log

Code1

暴力记的状态 TLE

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const ll mod=1e9+7; int a[33],b[33]; int f[33][33][2][2]; int dfs(int u,int m,int lim1,int lim2) {if(!u) return (m);if(f[u][m][lim1][lim2]!=-1) return f[u][m][lim1][lim2];f[u][m][lim1][lim2]=0;int v1=lim1?a[u]:1;int v2=lim2?b[u]:1;int ans=0;for(int i=0;i<=v1;i++)for(int j=0;j<=v2;j++)if(!(i&j)){int cur=m;if(i==1||j==1) cur=max(m,u);ans=(1ll*ans+dfs(u-1,cur,lim1&&(i==a[u]),lim2&&(j==b[u])))%mod;}return f[u][m][lim1][lim2]=ans; } int solve(int x,int y) {int m=0;while(x||y){a[++m]=(x&1);b[m]=(y&1);x>>=1;y>>=1;}for(int i=0;i<=m;i++) for(int j=0;j<=m;j++) for(int p=0;p<=1;p++) for(int q=0;q<=1;q++) f[i][j][p][q]=-1;return dfs(m,0,1,1); } int main() {int Tc=rd();while(Tc--){int x=rd(),y=rd();printf("%d\n",solve(x,y));}return 0; }

Code2

稍微优化了一下 AC

#include<bits/stdc++.h> #pragma GCC optimize(2)using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const int mod=1e9+7; int a[33],b[33]; int f[33][2][2][2]; int dfs(int u,int m,int lim1,int lim2) {if(!u) return (1);if(f[u][m][lim1][lim2]!=-1) return f[u][m][lim1][lim2];int v1=lim1?a[u]:1;int v2=lim2?b[u]:1;int ans=0;for(int i=0;i<=v1;i++)for(int j=0;j<=v2;j++)if(!(i&j)){int c=1;if(m==0&&(i==1||j==1)) c=u;ans=(1ll*c*dfs(u-1,m||i==1||j==1,lim1&&(i==a[u]),lim2&&(j==b[u]))%mod+ans)%mod;}return f[u][m][lim1][lim2]=ans; } int solve(int x,int y) {int m=0;while(x||y){a[++m]=(x&1);b[m]=(y&1);x>>=1;y>>=1;}memset(f,-1,sizeof f);return dfs(m,0,1,1); } int main() {int Tc=rd();while(Tc--){int x=rd(),y=rd();printf("%d\n",(solve(x,y)-1+mod)%mod);}return 0; }

总结

以上是生活随笔为你收集整理的C. Sum of Log（数位dp）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。