|
|
思路：
f[a][b] = { 種類(lèi)數(shù)目為 a，螞蟻數(shù)目為 b 時(shí)候的方案總數(shù) }
轉(zhuǎn)移：
f[a][b] = f[a - 1][0] + f[a - 1][1] + ... + f[a - 1][b]
時(shí)間 O(AT) 如果求 f[a][*] 只用一次循環(huán)的話
可以用循環(huán)數(shù)組
杯具：
把i看成j了，足足調(diào)了3個(gè)小時(shí)，注意，是不吃不喝，也沒(méi)有上廁所，沒(méi)有聽(tīng)歌，沒(méi)有看優(yōu)酷。。
是精神高度集中地浪費(fèi)了3個(gè)小時(shí)！
與非主流之腦殘相比，有過(guò)之而無(wú)不及也。
 #include <stdio.h>
#define P 1000000
int T, A, S, B, fam[1024], dp[2][1024*128], *cur, *pre;
inline int min(int a, int b)
   {
 return a < b ? a : b;
 }
int main()
{
int i, j, cnt, end, sum;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d%d", &T, &A, &S, &B);
  for (i = 0; i < A; i++) {
scanf("%d", &j);
fam[j]++;
 }
for (i = 0; i <= fam[1]; i++)
dp[1][i] = 1;
end = fam[1];
for (i = 2; i <= T; i++) {
cur = dp[i & 1];
pre = dp[(i+1) & 1];
cur[0] = pre[0];
end += fam[i];
for (j = 1; j <= end; j++) {
cur[j] = cur[j - 1] + pre[j];
if (j > fam[i])
cur[j] -= pre[j - fam[i] - 1];
cur[j] += P;
cur[j] %= P;
}
}
sum = 0;
for (i = S; i <= B; i++) {
sum += cur[i];
sum %= P;
}
printf("%d\n", sum);
return 0;
}
|