题解 [AHOI2009]同类分布

不理解之前为什么不会哈哈哈哈哈哈哈哈。

我是个天才（喜

显然记录 \(f_{i, t, r, s, limit, lead}\)，\(i, limit, lead\) 是数位 dp 的套路，\(t\) 代表被除数，就是原数，\(r\) 代表余数，\(s\) 代表除数。

我们会发现 \(s\) 直接转移非常难做，而且它很小，最多才 \(9 \times 18 = 162\)，直接枚举。

然后我们会发现 \(t\) 非常大怎么办 \(t\) 不重要就是 \(t\) 的各个数位和重要，数位和顶多 162，我们将 \(t\) 改为各个数位和即可。

然后我们就可以把 \(s\) 这一维删掉。

转移显而易见。

开 longlong+O2 即可

//SIXIANG

#include <iostream>

#include <cstring>

#define MAXN 10000

#define ll long long

#define QWQ cout << "QWQ" << endl;

using namespace std;

ll f[20][200][200][2][2];

int tot = 0, arr[MAXN + 10];

int pika(int i, int t, int r, bool limit, bool lead, int qaq) {

	if(!i) {

		if(!r && t == qaq) return 1;

		else return 0;

	}

	if(f[i][t][r][limit][lead] != -1) return f[i][t][r][limit][lead];

	ll rest = 0;

	int lim = ((limit) ? (arr[i]) : 9);

	for(int p = 0; p <= lim; p++)

		rest = (rest + pika(i - 1, t + p, (10 * r + p) % qaq, limit && (p == arr[i]), lead && (!p), qaq));

	f[i][t][r][limit][lead] = rest;

	return rest;

}

ll solve(int x) {

	memset(arr, 0, sizeof(arr));

	tot = 0;

	do {

		arr[++tot] = x % 10;

		x /= 10;

	} while(x);

	ll sum = 0;

	for(int p = 1; p <= 9 * tot; p++) {

		memset(f, -1, sizeof(f));

		sum += pika(tot, 0, 0, 1, 1, p);

	}

	return sum;

}

signed main() {

	int l, r;

	cin >> l >> r;

	cout << solve(r) - solve(l - 1) << endl;

}

巴特西

题解 [AHOI2009]同类分布

最新文章

热门文章