SDOI2010 代码拍卖会
题意:
题目传送门
题解：
看完题目之后，第一反应应该就是数位\(Dp\)了，但是考虑到\(N\)非常的大，我们需要考虑另一种方法。注意到这个满足条件的数字的每一位都大于等于前一位，所以我们可以比较明显的发现，最后组成的数字一定可以表示成小于等于\(9\)个\(111...111\)（若干个\(1\)）这样形式的数字之和，随后可以发现这些数字在模\(p\)的意义下是有循环节的，所以我们可以设计一个\(Dp\)，记\(cnt[i]\)表示模\(p\)为\(i\)的\(111...111\)这样的数字的个数，\(f[i][j][k]\)表示考虑了模\(p\)小于等于\(i\)的数，当前数字模\(p\)为\(j\)，已经选了\(k\)个\(111...111\)这样的数字的方案数，转移方程就是\(f[i][j][k] * \binom{cnt[i] + t - 1}{t} \to f[i + 1][(j + t \times i) \% p][k + t]\)。最后注意由于每一个数都是\(1\)，所以\(1111...111\)（\(N\)个\(1\)）是必选的。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const int Md = 999911659;
typedef long long ll;
inline int Add(const int &x, const int &y) { return (x + y >= Md) ? (x + y - Md) : (x + y); }
inline int Sub(const int &x, const int &y) { return (x - y < 0) ? (x - y + Md) : (x - y); }
inline int Mul(const int &x, const int &y) { return (ll)x * y % Md; }
int Powe(int x, int y) {
int ans = 1;
for(;y; y >>= 1, x = Mul(x, x)) if(y & 1) ans = Mul(ans, x);
return ans;
}
int f[N][N][10], cho[N][10], inv[10];
ll n;
ll cnt[N], st[N], num[N];
int p, sum, St, Ed;
int main() {
scanf("%lld%d", &n, &p);
for(int i = 1; i <= n; i++) {
sum = sum * 10 + 1; sum %= p;
if(st[sum]) {
St = st[sum]; Ed = i;
break;
}
cnt[sum]++; st[sum] = i; num[i] = sum;
}
int len = 0;
if(St) {
len = Ed - St;
ll c = n - Ed + 1;
ll d = c / len, m = c % len;
for(int i = St; i < Ed; i++) cnt[num[i]] += d;
for(int i = St; i < Ed && m; i++, m--) cnt[num[i]] ++;
}
cnt[0]++;
inv[1] = 1;
for(int i = 2; i <= 9; i++) inv[i] = Mul(Md - Md / i, inv[Md % i]);
for(int i = 0; i < p; i++) {
cnt[i] %= Md;
cho[i][0] = 1;
for(int j = 1; j <= 8; j++) {
cho[i][j] = Mul(Mul(cnt[i] % Md, cho[i][j - 1]), inv[j]);
cnt[i] = Add(cnt[i], 1);
}
}
if(!len) {
f[0][num[n]][0] = 1;
for(int i = 0; i < p; i++) {
for(int j = 0; j < p; j++) {
for(int k = 0; k <= 8; k++) {
for(int t = 0; t <= k; t++) {
if(!f[i][(j - t * i % p + p) % p][k - t]) continue;
f[i + 1][j][k] = Add(f[i + 1][j][k], Mul(f[i][(j - t * i % p + p) % p][k - t], cho[i][t]));
}
}
}
}
printf("%d\n", f[p][0][8]);
return 0;
}
int las = (n - Ed + 1) % len;
if(!las) las += len;
f[0][num[St + las - 1]][0] = 1;
for(int i = 0; i < p; i++) {
for(int j = 0; j < p; j++) {
for(int k = 0; k <= 8; k++) {
for(int t = 0; t <= k; t++) {
if(!f[i][(j - t * i % p + p) % p][k - t]) continue;
f[i + 1][j][k] = Add(f[i + 1][j][k], Mul(f[i][(j - t * i % p + p) % p][k - t], cho[i][t]));
}
}
}
}
printf("%d\n", f[p][0][8]);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10639135.html
相关资源：JAVA上百实例源码以及开源项目
