本文主要是介绍Project Euler 865 Triplicate Numbers（线性dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
能通过每次消除3个一样的数字，最终把数字消成空的数字是合法的，
求串长度不超过n的，没有前导0的数字中，合法的数字的个数
n=10000，答案对998244353取模，只需要输出数字
思路来源
乱搞AC
题解
暴力先把n=9求出来，有了n=9和n=30，都对上之后就敢交n=1e4了
dp[i]表示长度为i的合法方案，显然i是3的倍数是才有合法方案
然后还要分有没有前导0，于是就多开了一维，虽然后来发现dp[i][0]没有用到
dp[i][0]表示没有前导0限制的方案数，dp[i][1]表示有前导0限制的方案数
考虑最后一个数是怎么填的，只有四种情况，
其中xxx的长度也需要满足3的倍数，
①xxx111
②1xxx11
③11xxx1
④1xxx1yyy1
此外，为了避免重复，
需要保证这三个1在这一段中是位置处于最后的，能被消掉的3个1
第一种情况显然满足，第二三四种情况，都需要保证，
中间的xxx、yyy不管怎么消，都不能有1漏在最左边或最右边
比如11001111，100011122211这些，下划线的3个1不是位于最后的3个1，就会计数重复
而101110011就是合法的，中间011100怎么消，都不会导致1出现在最左或最右，
只要和想消的3个1不相邻，就能构成一组唯一计数的方案
所以，定义f[i]用于辅助转移，
f[i]表示长度为i时，0-9随便填，能消完，
但是不管怎么消，中途1都不能出现在最左或最右的方案数
然后就分情况转移的四种情况讨论即可，
第一种情况转移是O(1)的，
第二三种情况1xxx11和11xxx1是可以合并成一种转移，给系数乘2的，转移是O(n)的，
第三种情况暴力转移是O(n^2)的，但可以一边求一边暴力维护卷积mul，这样转移就是O(n)的了
第二三种情况合并一下，那就是三种情况，
除去第一种情况O(1)转移外，都要考虑前导0的问题
每种情况填的数字分是否占据了第一个位置讨论一下，
填的是第一个位置时，只能填9个数字，否则能填10个数字
求了f、dp[i][0]、dp[i][1]三个数组，
所以，总的转移式子一共3*(1+2*2)个
答案是dp数组的前缀和
代码1（dp）
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e4+10,M=10000,mod=998244353;
//dpi0:没前导0限制 dpi1:有前导0限制
//fi:两边只能填1-9，中间可以填0，两边不是0，且以任意顺序炸，0不会两边擦边的方案数
int t,f[N],dp[N][2],mul2[N],sum[N],ans;//ein,nit;
ll v;
int modpow(int x,int n,int mod){int res=1;for(;n;n>>=1,x=1ll*x*x%mod){if(n&1)res=1ll*res*x%mod;}return res;
}
void add(int &x,int y){x=(x+y)%mod;}
void sol(){//ein=8ll*modpow(9,mod-2,mod)%mod;//nit=9ll*modpow(10,mod-2,mod)%mod;dp[3][0]=10;dp[3][1]=9;sum[3]=f[3]=9;for(int i=6;i<=M;i+=3){add(f[i],9ll*f[i-3]%mod);//000-888add(dp[i][1],10ll*dp[i-3][1]%mod);//0-9add(dp[i][0],10ll*dp[i-3][0]%mod);//0-9//printf("i:%d dp:%d\n",i,dp[i]);for(int j=6;j<=i;j+=3){if(j==i){//只能填1-9//printf("j:%d dpj-3:%d\n",j,dp[j-3]);add(f[i],18ll*f[j-3]%mod);add(dp[i][1],18ll*f[j-3]%mod);//110001,100011 不能与相邻相同add(dp[i][0],20ll*f[j-3]%mod);//110001,100011 不能与相邻相同if(j>=9){add(f[i],9ll*mul2[j-3]%mod);add(dp[i][1],9ll*mul2[j-3]%mod);//100010001 不能与相邻相同add(dp[i][0],10ll*mul2[j-3]%mod);//100010001 不能与相邻相同}}else{//能填0-9add(f[i],18ll*f[j-3]%mod*f[i-j]%mod);add(dp[i][1],20ll*f[j-3]%mod*dp[i-j][1]%mod);//110001,100011 不能与相邻相同add(dp[i][0],20ll*f[j-3]%mod*dp[i-j][0]%mod);//110001,100011 不能与相邻相同if(j>=9){add(f[i],9ll*mul2[j-3]%mod*f[i-j]%mod);add(dp[i][1],10ll*mul2[j-3]%mod*dp[i-j][1]%mod);//100010001 不能与相邻相同add(dp[i][0],10ll*mul2[j-3]%mod*dp[i-j][0]%mod);//100010001 不能与相邻相同}}}for(int j=3;j<i;j+=3){//add(mul[i],1ll*ein*dp[j]%mod*ein%mod*dp[i-j]%mod);add(mul2[i],1ll*f[j]%mod*f[i-j]%mod);}//printf("i:%d dp0:%d dp1:%d mul:%d\n",i,dp[i][0],dp[i][1],mul2[i]);sum[i]=(sum[i-3]+dp[i][1])%mod;}
}
int main(){//sci(t);scanf("%lld",&v);v%=mod;printf("%d\n",(int)v);//cin>>t;sol();int m=M/3*3,ans=sum[m];printf("%d\n",ans);return 0;
}代码2（暴力打表）
打表知，T(6)=261，T(9)=9504
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e4+10,M=9,mod=998244353;
int t,ans,stk[15],c,cnt;
int main(){sci(t);int l=1,r=1e9;rep(i,l,r-1){int c=0;for(int j=i;j;j/=10){int v=j%10;if(c>=2 && stk[c]==stk[c-1] && stk[c]==v)c-=2;else stk[++c]=v;}if(!c){//printf("i:%d\n",i);cnt++;//if(cnt==10)break;}}printf("%d\n",cnt);return 0;
}
//T(6)=261
//T(9)=9504这篇关于Project Euler 865 Triplicate Numbers（线性dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
