考虑记搜实现，在过程中维护：
cur:目前到第几位
lim:是否卡着上界
sta:是否有前导零
...：你其他要维护的
windy数：https://www.luogu.org/problem/P2657
板题
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<map> using namespace std; typedef long long ll; typedef double db; #define pii pair<int,int> #define mp make_pair #define llinf 9000000000000000000LL #define B cout << "breakpoint" << endl; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } int num[20]; int f[20][20][2][2]; int dfs(int cur,bool start,bool lim,int pre) { if(f[cur][pre][start][lim] != -1) return f[cur][pre][start][lim]; if(cur == 0) return 1; int ans = 0; int res = lim ? num[cur] : 9; for(int i = 0;i <= res;i++) { if(start) { if(abs(pre - i) < 2) continue; ans += dfs(cur - 1,start,(i == res && lim),i); } else { if(i == 0) ans += dfs(cur - 1,start,(lim && i == res),i); else ans += dfs(cur - 1,1,(lim && i == res),i); } } return f[cur][pre][start][lim] = ans; } int ans; int solve(int x) { int k = 0; while(x) { num[++k] = x % 10; x /= 10; } memset(f,-1,sizeof(f)); return dfs(k,0,1,-10); } int main() { int a = read(),b = read(); if(a == 1) printf("%d",solve(b) - solve(a - 1) - 1); else printf("%d",solve(b) - solve(a - 1)); }
AHOI2009 同类分布：https://www.luogu.org/problem/P4127
考虑维护f[i][j][k]:到第i位，前面数字和是j，模完的答案是k
枚举模数即可
// luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<map> using namespace std; typedef long long ll; typedef double db; typedef int mainint; #define pii pair<int,int> #define int long long #define O(x) cout << #x << " " << x << endl; #define mp make_pair #define llinf 9000000000000000000LL #define B cout << "breakpoint" << endl; inline int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op; } const int N = 22; const int maxn = 205; int f[N][maxn][maxn][2],num[N],M; int dfs(int cur,int sum,int mod,bool lim) { if(cur == 0) return f[cur][sum][mod][lim] = (mod == 0 && sum == M); if(f[cur][sum][mod][lim] != -1) return f[cur][sum][mod][lim]; int res = lim ? num[cur] : 9; int ans = 0; for(int i = 0;i <= res;i++) ans += dfs(cur - 1,sum + i,(mod * 10 + i) % M,(lim && i == res)); return f[cur][sum][mod][lim] = ans; } int solve(int x) { int k = 0,tot = 0; while(x) { num[++k] = x % 10; tot += x % 10; x /= 10; } int ans = 0; for(M = 1;M <= k * 9;M++) { memset(f,-1,sizeof(f)); ans += dfs(k,0,0,1); } return ans; } mainint main() { int a = read(),b = read(); printf("%lld ",solve(b) - solve(a - 1)); }
萌数：https://www.luogu.org/problem/P3413
我们只要处理回文子串长度为2或3，即可包含所有情况
那么维护last和lalast，上一位和上两位，维护去掉前导零之后目前是第几位即可
注意，n较大时要字符串读入
// luogu-judger-enable-o2 #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; typedef int mainint; #define int long long const ll mod = 1000000007; #define O(x) cout << #x << " " << x << endl; #define B cout << "breakpoint" << endl; int dp[1005][10][10][3][2][2],a[1005]; int L,R,len; int dfs(int cur,int la,int lala,int sta,int lim,int have) { if(cur == 0) return have; if(dp[cur][la][lala][sta][lim][have]!=-1) return dp[cur][la][lala][sta][lim][have]; int ret=0; int res=lim?a[cur]:9; //printf("%lld %lld %lld %lld %lld %lld ",la,res,sta,lim,cur,have); for(int i=0; i<=res; i++) { if(sta==2) { if(!i) (ret+=dfs(cur-1,i,la,2,0,have))%=mod; else (ret+=dfs(cur-1,i,la,1,lim && i == res,have))%=mod; } else if( (i==lala && !sta) || i == la) (ret+=dfs(cur-1,i,la,0,lim&&i==res,1))%=mod; else (ret+=dfs(cur-1,i,la,0,lim&&i==res,have))%=mod; } dp[cur][la][lala][sta][lim][have]=ret; return ret; } char s[2005]; mainint main() { scanf("%s",s + 1); len = strlen(s + 1); memset(dp,-1,sizeof(dp)); for(int i = 1;i <= len;i++) a[i] = s[len - i + 1] - '0'; int i = 1; while(1) { if(a[i] > 0) {a[i]--; break; } else a[i] += 9,i++; } ll ans1 = dfs(len,0,0,2,1,0); scanf("%s",s + 1); len = strlen(s + 1); memset(dp,-1,sizeof(dp)); for(int i = 1;i <= len;i++) a[i] = s[len - i + 1] - '0'; ll ans2 = dfs(len,0,0,2,1,0); printf("%lld ",((ans2 - ans1) % mod + mod) % mod); return 0; }
储能表https://www.luogu.org/problem/P4067
咕