[IOI Camp Judge 60]背包 EX（駭客題）

IOI Camp Judge是暫時性的，因此我在這裡做了題目備份

這題駭客題測資很難構(我試過了......尤其$N$只給你$42$......)，而且要剛好在$1000000007$，隨機測資也很難碰撞

所以我寫了個智慧型測資構造器，只有在$DP$的最後一項$\leq 1000000007$時才繼續遞迴下去，當找到剛好碰撞的一組測資就輸出答案並進入無線迴圈卡死

這樣又太慢了(等了十分鐘還沒出來)，因此我弄了個亂數，以時間當作亂數種子，編成執行檔後用滑鼠點開十個視窗執行(時間不一樣所以用不同的亂數在跑)

十秒鐘後
其中兩個就找到解了XD

code:

#include <cstdio>
#include<cstdlib>
#include<ctime>
#define int long long
typedef long long LL;
const int N = 42;
const int M = 777;
const int MOD = (1e9 + 7)*1;
const int m=497;
int t,a[N], dp[M + 1];
LL Solve(const int n)
{
        for (int i = 0; i <= m; i++) dp[i] = 0;
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= a[i]; j--) {
                dp[j] += dp[j - a[i]];
                if (dp[j] > MOD)return MOD+1;
            }
        }
        return dp[m];
}
int nnn;
void Dfs(const int dep)
{
    if(dep==nnn)
    {
        if(Solve(nnn)==MOD)
        {
            printf("n=%lld,m=%lld\n",nnn,m);
            for(int i=0;i<nnn;i++)printf("%lld ",a[i]);puts("");
            for(;;);
            exit(0);
        }
        return;
    }
    a[dep]=(dep==0?0:a[dep-1])+(rand()&1?1:2);
//    while(Solve()>MOD)a[dep]++;
    for(;a[dep]<=m;a[dep]++)if(Solve(dep+1)<=MOD)
    {
    static int cnt=0,goal=0;
    if(cnt++>goal&&dep>nnn-4)goal+=1000,printf("dep=%lld,Solve()=%lld\n",dep,Solve(dep+1));
//        for(int i=dep+1;i<nnn;i++)a[i]=a[i-1]+1;
//        n=nnn;
//        if(Solve()<MOD)break;
        Dfs(dep+1);
    }
}
main() {
    srand(time(NULL));
//    freopen("in.txt","r",stdin);
    for(nnn=42;nnn>=1;nnn--)Dfs(0);
    puts("find nothing!");
    for(;;);
    return 0;
}