https://www.51nod.com/Contest/Problem.html#contestProblemId=4854
SB 卡我常
#include <bits/stdc++.h> #define int ll #define ll long long #define pb push_back using namespace std; const int mod=998244353; ll fpow(int x,int y) { ll res=1; x%=mod; while(y) { if(y&1) res=1ll*res*x%mod; y>>=1; x=1ll*x*x%mod; } return res; } const ll INV2=fpow(2,mod-2),INV3=fpow(3,mod-2),INV5=fpow(5,mod-2),INV7=fpow(7,mod-2); ll f[21][56][40][20][20]; ll mp[2][2][2][2]; ll cnt[56][40][20][20]; int nn[20],n,tot; ll dfs(int pos,int lim,int zero,int a,int b,int c,int d) { if(a<0||b<0||c<0||d<0) return 0ll; if(!pos) { // cout<<pos<<" retg "<<lim<<" "<<zero<<" "<<a<<" "<<b<<" "<<c<<" "<<d<<'\n'; if(zero) return 0ll; if(a==0&&b==0&&c==0&&d==0) return 1ll; return 0ll; } if(!lim&&!zero&&~f[pos][a][b][c][d]) return f[pos][a][b][c][d]; int mx=lim?nn[pos]:9,st=(!zero)?1:0; ll qwq=0; // cout<<pos<<" retg "<<lim<<" "<<zero<<" "<<st<<" "<<mx<<" "<<a<<" "<<b<<" "<<c<<" "<<d<<'\n'; for(int i=st;i<=mx;i++) { int na=a,nb=b,nc=c,nd=d; if(i==2) --na; if(i==3) --nb; if(i==4) na-=2; if(i==5) --nc; if(i==6) --na,--nb; if(i==7) --nd; if(i==8) na-=3; if(i==9) nb-=2; qwq=(qwq+dfs(pos-1,lim&(i==mx),zero&(i==0),na,nb,nc,nd))%mod; } if(!lim&&!zero) f[pos][a][b][c][d]=qwq; return qwq; } ll p2[62],p3[62],p5[62],p7[62]; signed main() { // int a=10000000; cout<<a*a%mod<<" "<<1ll*a*a%mod<<'\n'; cin.tie(0); ios::sync_with_stdio(false); memset(f,-1,sizeof(f)); p2[0]=p3[0]=p5[0]=p7[0]=1; for(int i=1;i<=60;i++) { p2[i]=1ll*p2[i-1]*2ll%mod; p3[i]=1ll*p3[i-1]*3ll%mod; p5[i]=1ll*p5[i-1]*5ll%mod; p7[i]=1ll*p7[i-1]*7ll%mod; } cin>>n; while(n) { nn[++tot]=n%10; n/=10; } // cout<<nn[1]<<" "<<nn[2]<<'\n'; for(int a=0;a<=tot*3;a++) { for(int b=0;b<=min(tot*2,tot*3-a);b++) { for(int c=0;c<=min(tot,tot*3-a-b);c++) { for(int d=0;d<=min(tot,tot*3-a-b-c);d++) { // if(!a&&!b&&!c&&!d) continue ; cnt[a][b][c][d]=dfs(tot,1,1,a,b,c,d); // cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<cnt[a][b][c][d]<<'\n'; // int qwq=p2[a]*p3[b]%mod*p5[c]%mod*p7[d]%mod; // mp[(a>0)][(b>0)][(c>0)][(d>0)]=(mp[(a>0)][(b>0)][(c>0)][(d>0)]+qwq*cnt[a][b][c][d]%mod)%mod; ll qwq=1ll*p2[a]*p3[b]%mod*p5[c]%mod*p7[d]%mod; bool aa=(a>0),bb=(b>0),cc=(c>0),dd=(d>0); mp[aa][bb][cc][dd]=(mp[aa][bb][cc][dd]+1ll*qwq*cnt[a][b][c][d]%mod)%mod; } } } } ll ans=0; for(int a=0;a<=tot*3;a++) { for(int b=0;b<=tot*2;b++) { for(int c=0;c<=tot;c++) { for(int d=0;d<=tot;d++) { // if(!a&&!b&&!c&&!d) continue ; if(!cnt[a][b][c][d]) break ; for(int i=0;i<=1;i++) { for(int j=0;j<=1;j++) { for(int k=0;k<=1;k++) { for(int z=0;z<=1;z++) { if(!mp[i][j][k][z]) continue ; // if(!i&&!j&&!k&&!z) continue ; ll nw=mp[i][j][k][z]; // cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<i<<" "<<j<<" "<<k<<" "<<z<<" "<<nw<<' '; if(a||i) nw=1ll%mod*nw*p2[a]%mod*INV2%mod; if(b||j) nw=1ll*nw%mod*2ll%mod*p3[b]%mod*INV3%mod; if(c||k) nw=1ll*nw%mod*4ll%mod*p5[c]%mod*INV5%mod; if(d||z) nw=1ll*nw%mod*6ll%mod*p7[d]%mod*INV7%mod; nw=1ll*nw*cnt[a][b][c][d]%mod; // cout<<nw<<'\n'; // cout<<nw<<" "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<cnt[a][b][c][d]<<'\n'; // if((ans+nw)>=mod) ans=ans+nw-mod; else ans=ans+nw; ans=(ans+nw)%mod; } } } } } } } } cout<<ans; return 0; }