淘宝店铺做网站收录,网站案例网站建设,wordpress 标题字数,济南制作网站软件题目 能通过每次消除3个一样的数字#xff0c;最终把数字消成空的数字是合法的#xff0c;
求串长度不超过n的#xff0c;没有前导0的数字中#xff0c;合法的数字的个数
n10000#xff0c;答案对998244353取模#xff0c;只需要输出数字
思路来源
乱搞AC
题解
暴力…题目 能通过每次消除3个一样的数字最终把数字消成空的数字是合法的
求串长度不超过n的没有前导0的数字中合法的数字的个数
n10000答案对998244353取模只需要输出数字
思路来源
乱搞AC
题解
暴力先把n9求出来有了n9和n30都对上之后就敢交n1e4了
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漏在最左边或最右边 比如11001111100011122211这些下划线的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*(12*2)个
答案是dp数组的前缀和
代码1dp
#includebits/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 pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#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 N1e410,M10000,mod998244353;
//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 res1;for(;n;n1,x1ll*x*x%mod){if(n1)res1ll*res*x%mod;}return res;
}
void add(int x,int y){x(xy)%mod;}
void sol(){//ein8ll*modpow(9,mod-2,mod)%mod;//nit9ll*modpow(10,mod-2,mod)%mod;dp[3][0]10;dp[3][1]9;sum[3]f[3]9;for(int i6;iM;i3){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 j6;ji;j3){if(ji){//只能填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(j9){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(j9){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 j3;ji;j3){//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);//cint;sol();int mM/3*3,anssum[m];printf(%d\n,ans);return 0;
}
代码2暴力打表
打表知T(6)261T(9)9504
#includebits/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 pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#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 N1e410,M9,mod998244353;
int t,ans,stk[15],c,cnt;
int main(){sci(t);int l1,r1e9;rep(i,l,r-1){int c0;for(int ji;j;j/10){int vj%10;if(c2 stk[c]stk[c-1] stk[c]v)c-2;else stk[c]v;}if(!c){//printf(i:%d\n,i);cnt;//if(cnt10)break;}}printf(%d\n,cnt);return 0;
}
//T(6)261
//T(9)9504
