洛谷p1773 dp

其实， 这个dp还是蛮简单的，dp做多了后就会觉得方程不难出了，其实我的思路和大家都差不多，但是大部分都用了O(N^2)去预处理出这个区间内的值取模后是多少，其实这是完全没有必要的。听我来给你吹

f[i][j] = v：前i个字符各种操作后的数字为j，使用的最少的乘法个数为v，最后一个字符必须要落在i后面！！！！
为什么我们要强行让他最后一个乘法字符在i后面，因为如果不这么做，我们就无法知道他最后一个乘法字符在哪里，你就算不出一个值与前面的值相乘。
接下来考虑怎么转移
f[i][j] = min(f[k][z] + 1),
其中k<i,然后（z * [k+1,i]）%mod ==j
放一个乘法字符在i后面，然后枚举前面的位置哪些可以算到最后的答案是j
很显然你只需要枚举一次前面所有的状态就可以得到i可以满足的每一个j，**不需要对于每一个j就去枚举一次所有状态！！！！**下一步，怎么得到某些区间的数字取mod后的结果是多少。
其实仔细观察可以知道，我们i是从1到len开始枚举的，然后对于每一个f[i][j]， 后面需要利用到f[i][j]都是从i后面的数字到当前位置的数字，那么就是我们可以有一个num数组,这个数组存的内容就是
num[z] = v, 从z+1到当前位置的字符串取模后的值
当前的位置为i，那么在前面所有位置的num[z]，都只需要*10+当前的字符，再去取模，那么就是当前需要的那个数字答案啦！

int v = (num[j] * 10 + (node[i] - '0')) % m;
			num[j] = v;

上面代码的i就是当前位置，j就是枚举前面所有的位置。
这样子去转移就是纯的O(N^2M)，不需要额外加上
n^2的预处理！
小提醒，他是对m取模！！！我当初用之前设置的mod取模wa了好多次完全不知道哪错了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<string>
#include<stack>
#include<cmath>
#include<map>
#include<set>
#define int long long
//#define double long double
using namespace std;
#define PI 3.1415926535898 
#define eqs 1e-6
const long long max_ = 1000 + 7;
const int mod = 998244353;
const int inf = 1e9;
const long long INF = 1e18;
int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
int min(int a, int b) {
	return a < b ? a : b;
}
int max(int a, int b) {
	return a > b ? a : b;
}
char node[max_];
int num[max_],f[max_][60],m;
signed main() {
	std::ios::sync_with_stdio(false);
	cin >> node + 1;
	cin >> m;
	int len = strlen(node + 1);
	memset(f, 23, sizeof(f));
	//memset(num, 0, sizeof(num));
	f[0][1] = -1;
	for (int i = 1; i <= len; i++) {
		for (int j = 0; j < i; j++) {
			int v = (num[j] * 10 + (node[i] - '0')) % m;
			num[j] = v;
			for (int z = 0; z < m; z++) {
				if (f[j][z] > len) continue;
				int vv = ((z % m)*(v % m)) % m;
				f[i][vv] = min(f[i][vv], f[j][z] + 1);
			}
		}
	}
	for (int i = 0; i < m; i++) {
		if (f[len][i] < len) {
			cout << i << " " << f[len][i] << " "; break;
		}
	}
	for (int i =m - 1; i >= 0; i--) {
		if (f[len][i] < len) {
			cout << i << " " << f[len][i]; break;
		}
	}
	return 0;
}