[Luogu P3286] [BZOJ 3598] [SCOI 2014] 팡백의 백화점 여행

로곡 전송문
BZOJ 전송문
제목 설명
팡씨 아저씨는 어느 날 한 백화점에서 열리는 게임에 참가하러 갔다.상가에서 몇 명의 직원을 파견하여 한 줄로 늘어섰다.사람마다 앞에 돌무더기가 몇 무더기 있다.
공교롭게도 이 i i i 의 사람들 앞에 있는 제 j j 더미의 돌의 수량은 마침 이 i i가 K K K 진법으로 쓴 후 제 j j 위였다.지금 팡백은 게임을 하려고 하는데 백화점에서 팡백에게 정수 L, R L, R L, R 을 두 개 줄 것이다.
방백부는 위치를 [L, R] [L, R] [L, R] 중의 모든 사람의 돌을 합쳐서 돌무더기를 만들려고 한다.매번 조작할 때마다 그는 한 사람 앞에 있는 두 무더기의 돌을 선택하여 그 중의 한 무더기 중의 일부 돌을 다른 무더기로 옮길 수 있다. 그 대가는 이동하는 돌의 수량*이동의 거리이다.
백화점은 방 아저씨가 임무를 완수하기만 하면 야자를 주겠다고 약속했다. 대가가 적을수록 야자를 더 많이 주겠다.그래서 방 씨 아저씨는 매우 조급해서 당신이 그에게 가장 적은 대가가 얼마인지 알려주고 싶어 합니다.예를 들어 10 10 10진법 아래 12312 12312에 있는 사람이 돌을 합병하는 데 가장 적은 대가는 1 ∗ 2 + 2 ∗ 1 + 3 ∈ 0 + 1 ∈ 1 + 2 ∈ 2 = 9 1 * 2 + 2 * 2 * 1 + 3 * 0 + 1 * 1 + 2 * 2 * 2 * 2 = 9 1\872+2 + 2 + 2 = 9 1 ∈ 1 + 2 + 2 + 2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 + 1 + 2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 + 2 + 2 + 1 + 2 + 2 + 2 + 2 + 1 + 2 + 2 + 2 + 1 ͨ + 2 + 1 + 2 + 2 + 1 + 2 + 2 + 2 + 1
입력 출력 형식
입력 형식:
입력은 133개의 공백으로 구분된 정수 L, R, K L, R, K L, R, K L, R, K로 구성되어 있으며 백화점에서 방 아저씨에게 주는 222개의 정수와 진수를 나타냅니다.
출력 형식:
출력은 111줄에 불과하고 111개의 정수를 포함하여 최소한의 대가를 나타낸다.
출력 샘플 가져오기
샘플 #1 입력:

3 8 3

샘플 내보내기 #1:

5

설명
1 ≤ L ≤ R ≤ 1 0 15 , 2 ≤ K ≤ 20 1\le L\le R\le 10^{15}, 2\le K\le 20 1≤L≤R≤1015,2≤K≤20
문제 풀이 분석
ttcl, 이 문제를 오랫동안 생각했는데...
분명히 디지털 dp dp dp입니다.kk자릿수가 있는 PP에 대해 모든 자릿수의 숫자를 mmm위에 두면 공헌은 ∑i=1k∣i-m∣이다× d g t [ i ]\sum_{i=1}^{k}|i-m|\times dgt[i] ∑i=1k​∣i−m∣×dgt[i].
그러면 우리는 먼저 모든 수를 마지막 자리에 놓고 한 자리씩 앞으로 옮길 수 있다.ii i에서 i-3 i-1 i-1 i-3 1위로 이동한 감소 기여는 상위 i-1 i-1 i-3 1위의 숫자와 차감된 K-3 i+1 K-i+1 K-3 i+1의 숫자와 차감된 K-3 i+1 K-i+1의 숫자다.이 값이 0보다 작으면 re t u r n return return으로 바로 이동하면 됩니다.
K≤20 K\le 20 K≤20이기 때문에 모든 수위와 크기가 크지 않습니다. 직접 dp[i][j]dp[i][j]dp[i][j]를 설정하면 앞의 ii자리 수와 jjj에 대한 기여의 합을 나타낼 수 있습니다.
코드는 다음과 같습니다.

#include 
#include 
#include 
#include 
#include 
#include 
#define R register
#define IN inline
#define W while
#define gc getchar()
#define ll long long
int num[70];
int K;
ll l, r;
ll dp[50][2050];
ll DFS(R int dgt, R int sum, R bool lim)
{
	if (!dgt) return sum;
	if ((!lim) && (~dp[dgt][sum])) return dp[dgt][sum];
	int up = lim ? num[dgt] : K - 1;
	ll ret = 0;
	for (R int i = 0; i <= up; ++i)
	ret += DFS(dgt - 1, sum + (dgt - 1) * i, lim & (i == up));
	if (!lim) dp[dgt][sum] = ret;
	return ret;
}
ll DFS(R int dgt, R int sum, R int pos, R bool lim)
{
	if (sum < 0) return 0;
	if (!dgt) return sum;
	if ((!lim) && (~dp[dgt][sum])) return dp[dgt][sum];
	int up = lim ? num[dgt] : K - 1;
	ll ret = 0;
	for (R int i = 0; i <= up; ++i)
	if (dgt >= pos) ret += DFS(dgt - 1, sum + i, pos, lim & (i == up));
	else ret += DFS(dgt - 1, sum - i, pos, lim & (i == up));
	if (!lim) dp[dgt][sum] = ret;
	return ret;
}
ll solve(R ll val)
{
	int cnt = 0;
	std::memset(dp, -1, sizeof(dp));
	W (val) num[++cnt] = val % K, val /= K;
	ll ret = DFS(cnt, 0, 1);
	for (R int i = 2; i <= cnt; ++i)
	std::memset(dp, -1, sizeof(dp)), ret -= DFS(cnt, 0, i, 1);
	return ret;
}
int main(void)
{
	scanf("%lld%lld%d", &l, &r, &K);
	printf("%lld", solve(r) - solve(l - 1));
}