广州网站建设互广,郑州企业网站优化哪家便宜,俱乐部网站模板,利津网站定制传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
比较套路的题#xff0c;首先也有个明显的状态f[pos][num][sum]f[pos][num][sum]f[pos][num][sum]表示到了pospospos位#xff0c;当前数为numnumnum#xff0c;各位数字之和为sumsumsu…传送门
文章目录题意思路题意 思路
比较套路的题首先也有个明显的状态f[pos][num][sum]f[pos][num][sum]f[pos][num][sum]表示到了pospospos位当前数为numnumnum各位数字之和为sumsumsum。由于a,b≤1e18a,b\le1e18a,b≤1e18所以显然是不行的。看到整除就可以考虑是否可以通过将第二维取模来优化状态呢我们发现第三维最多只有9∗189*189∗18个数所以我们枚举第三维的约数让后将numnumnum模上约数即可这样状态只有20∗9∗18∗9∗1820*9*18*9*1820∗9∗18∗9∗18个了再乘上枚举约数9∗189*189∗18复杂度约为850305608503056085030560显然可以过掉。
// Problem: P4127 [AHOI2009]同类分布
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4127
// Memory Limit: 125 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;LL a,b;
int A[20],tot;
int limit;
LL f[20][9*1810][9*1810];LL dp(int pos,int num,int sum,int flag) {if(sumlimit) return 0;if(pos0) return num0sumlimit;if(f[pos][num][sum]!-1flag) return f[pos][num][sum];int xflag? 9:A[pos];LL ans0;for(int i0;ix;i) {ansdp(pos-1,(num*10i)%limit,sumi,flag||ix);}if(flag) f[pos][num][sum]ans;return ans;
}LL solve(LL x) {tot0;while(x) A[tot]x%10,x/10;return dp(tot,0,0,0);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);//cout20*9*18*9*18*9*18endl;cinab;LL ans0;for(int i1;i9*18;i) {limiti; memset(f,-1,sizeof(f));anssolve(b)-solve(a-1);}coutansendl;return 0;
}
/**/
