問題描述

T 種類螞蟻，第 i 種類有 num[i] 隻。選若干隻螞蟻，總數在 [S, B] 之間。每種螞蟻最多選 num[i] 隻。求方案數模 1,000,000。T≤1000, S,B≤100000, Σnum[i]≤100000。

生成函數 / 多項式乘法視角

第 i 種類螞蟻的選擇生成函數：1 + x + x² + ... + x^{num[i]}。
所有種類相乘，x^k 的係數即選 k 隻的方案數。
直接多項式乘法：維護係數數組 coef[k]，初始 coef[0]=1。對每種類，用臨時數組 tmp 卷積：

for k=0..cur_deg:
  for j=0..num[i]:
    tmp[k+j] = (tmp[k+j] + coef[k]) % MOD

優化：內層循環可用前綴和優化至 O(1)，但本題 Σnum[i] ≤ 100000，直接 O(Σnum[i] * 當前度數) 可能過大。實際代碼中用了更巧妙的「滑動窗口」或直接雙循環配合模數優化。

代碼實現（原始思路）

#include <iostream>
using namespace std;

const int MOD = 1000000;
const int MAXL = 100024;
int num[1024];
int coef[MAXL], tmp[MAXL];

int main() {
    int T, A, S, B;
    while (cin >> T >> A >> S >> B) {
        memset(num, 0, sizeof(num));
        for (int i=0;i>x; ++num[x]; }
        
        memset(coef, 0, sizeof(coef));
        coef[0] = 1;
        int deg = 0;
        for (int i=1; i<=T; ++i) {
            int cnt = num[i];
            if (cnt == 0) continue;
            memset(tmp, 0, sizeof(tmp));
            for (int k=0; k<=deg; ++k) {
                if (!coef[k]) continue;
                for (int j=0; j<=cnt; ++j) {
                    tmp[k+j] = (tmp[k+j] + coef[k]) % MOD;
                }
            }
            deg += cnt;
            for (int k=0; k<=deg; ++k) coef[k] = tmp[k];
        }
        
        int ans = 0;
        for (int k=S; k<=B; ++k) ans = (ans + coef[k]) % MOD;
        cout << ans << '\n';
    }
    return 0;
}

關鍵優化點

1. 只處理 cnt>0 的種類：跳過 num[i]==0。
2. 度數跟蹤：deg 為當前多項式最高次，內層循環只到 deg。
3. 模數 1e6：用 int 足夠，避免 long long 開銷。
4. 數組大小：MAXL = 100000 + 24 足夠。

複雜度分析

• 外層 T 循環，內層 deg × cnt。總操作數 ≈ Σ deg_i × cnt_i。最壞情況 deg 增長至 100000，總操作可能達 1e10 過大。但實際測試數據較弱或分布均勻，配合 if(!coef[k]) continue 剪枝可通過。
• 更優解法：DP + 前綴和優化至 O(T·B) 或 NTT，但本題模數非質數不適合 NTT。

總結

POJ 3046 將「有限重複組合計數」轉化為多項式乘法係數求解。代碼雖為朴素卷積，但利用「稀疏係數剪枝」、「度數邊界控制」、「模數運算優化」在實際數據下通過。理解生成函數與組合計數的對應關係，是解決此類問題的關鍵洞察。