题目大意
对于不定方程a1+a2+…+ak-1+ak=g(x)，其中k≥2且k∈N，x是正整数，g(x)=x^x mod 1000(即x^x除以1000的余数)，x，k是给定的数。我们要求的是这个不定方程的正整数解组数。
DP（暴力）解法
定义F(p, rest)为第p个数，p及p后面的数的和为rest的解的数量，递归式为：F(p, rest)=if(rest==0)0 else if (p == k) rest else sum foreach curVal(0<curVal<=rest) F(p, rest - curVal)。
不用高精度，本方法能得40分。
注意
curVal<=rest就可以了，反正如果curVal大了以后也能返回0，不要擅自进一步缩小curVal的范围。
#include#include using namespace std;#define ll long long#define _NDEBUGconst int MAX_K = 110, MAX_X = 1010, P = 1000;ll F[MAX_K][MAX_X];ll K, X;ll Mult(ll a, ll b, ll p){ ll ans = 0; while (b) { if (b & 1) ans = (ans + a) % p; a = (a + a) % p; b >>= 1; } return ans;}ll Power(int a, int n, int p){ ll ans = 1; while (n) { if (n & 1) ans = Mult(ans, a, p); a = Mult(a, a, p); n >>= 1; } return ans;}ll DP(int p, ll rest){ if (F[p][rest] != -1) return F[p][rest]; if (rest == 0) return F[p][rest] = 0; if (p == K) return F[p][rest] = 1; F[p][rest] = 0; for (int i = 1; i <= rest; i++) F[p][rest] += DP(p + 1, rest - i); return F[p][rest];}int main(){ scanf("%lld%lld", &K, &X); memset(F, -1, sizeof(F)); printf("%lld\n", DP(1, Power(X, X, P))); return 0;}
组合数学解法
把x^x%1000看作一个线段，a1,a2...看作一个个隔板划分出的区域，这就是组合数学中的隔板模型，最终结果为C(k,x^x%1000)
注意
- 求组合数的模板就这样定死了，不要改。
- 高精度里最好把=运算符写上。
#include#include #include using namespace std;#define ll long longconst int MAX_K = 110, MAX_X = 1010, P = 1000, BASE = 10000, CARRY = 4, MAX_LEN = 1010;ll K, X;ll Mult(ll a, ll b, ll p){ ll ans = 0; while (b) { if (b & 1) ans = (ans + a) % p; a = (a + a) % p; b >>= 1; } return ans;}ll Power(int a, int n, int p){ ll ans = 1; while (n) { if (n & 1) ans = Mult(ans, a, p); a = Mult(a, a, p); n >>= 1; } return ans;}struct BigInt{private: int A[MAX_LEN]; int Len;public: void Clear() { memset(A, 0, sizeof(A)); Len = 0; } void Set(int x) { Clear(); while (x) { A[Len++] = x%BASE; x /= BASE; } while (A[Len] == 0 && Len > 0) Len--; } BigInt() { Clear(); } BigInt operator = (const int x) { Set(x); return *this; } BigInt operator = (const BigInt &a) { memcpy(A, a.A, sizeof(A)); Len = a.Len; return *this; } void Print() { printf("%d", A[Len]); for (int i = Len - 1; i >= 0; i--) printf("%0*d", CARRY, A[i]); printf("\n"); } BigInt operator += (const BigInt &a) { Len = max(Len, a.Len); for (int i = 0; i <= Len; i++) { A[i] += a.A[i]; A[i + 1] += A[i] / BASE; A[i] %= BASE; } if (A[Len + 1]) Len++; return *this; } BigInt operator + (const BigInt &a) { BigInt Num = *this; return Num += a; }};BigInt Comb(int r, int n){ static BigInt C[MAX_K]; C[0] = 1; for (int i = 1; i <= n; i++) { for (int j = min(r, i); j > 0; j--) { if (i == j) C[j] = 1; else C[j] = C[j - 1] + C[j]; } } return C[r];}int main(){ scanf("%lld%lld", &K, &X); Comb(K - 1, Power(X,X,P) - 1).Print(); return 0;}