冲鸭！去刷题：https://ac.nowcoder.com/acm/contest/625/A
第一行是一个整数T (1≤T≤50)，表示数据组数。
接下来T行，每行两个整数L,R (1≤L≤R≤232−1)L,R (1≤L≤R≤232−1)，表示一组询问。
输出共T行。对于每个询问，输出一行一个整数ans，表示CC邀请参加线下训练营的NB群友人数模109+7109+7的结果。
解题思路：
看到无穷多位，有点蒙。
不过考虑 R 的范围最大到 2^32 而且每一位不取 0 或者 1，所以位数是有限的，而且不多。
这道题的正解也正是暴搜。
暴搜出 sum[ R, 1 ], sum[ L-1, 1 ], 两者作差。
搜索过程即枚举每一位的数 d.
而每位求积的过程有很多状态是重复的，记录一下状态值，减少暴力。
最后再取模可以过。
AC code:
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define LL long long using namespace std; //const LL MAXN = 1<<32; const LL mod = 1e9+7; //map<int, int>mmp; map<LL, LL>mmp; LL dfs(LL now) { if(mmp.count(now)){ return mmp[now]; } LL res = 0; for(LL i = 2; i <= 9; i++){ if(now >= i){ res+=dfs(now/i)+1; // res%=mod; } } return mmp[now] = res; } int main() { LL L, R; int T_case; scanf("%d", &T_case); while(T_case--){ scanf("%lld %lld", &L, &R); LL ans = (dfs(R)-dfs(L-1))%mod; printf("%lld\n", ans); } return 0; }
A NB群友 【记忆化搜索】（2019年华南理工大学程序设计竞赛（春季赛））
原文：https://www.cnblogs.com/ymzjj/p/10713187.html