HGOI 20191106

t1 旅行家（traveller）

2s,256MB

【题目背景】

小X热爱旅行，他梦想有一天可以环游全世界……

【题目描述】

现在小X拥有n种一次性空间转移装置，每种装置可以使他前进ai光年，每种装置他拥有bi个。（小X作为一个旅行家，是不会后退的；他的初始坐标是0）

他突然对宇宙的根源感到十分好奇，他发现他用完所有的装置刚好能够到达，于是她就开始了他的旅行。

邪恶的光明法师小S听说了这件事，他决定阻止可爱的小X，于是他使出了扭转乾坤的神通，在前进道路上的m个节点上创造出了可以吞噬一切的黑洞，它们的坐标分别是ci。

小X当然不希望旅行失败，为了嘲讽小S，他想知道他有多少种不同的方式到达宇宙的根源。但是小X也不想过分麻烦你，所以他只想知道答案对100000007取模以后的结果。

注意：每种装置本质相同，即连续使用多次同种装置，但顺序不同算作1种。

【输入格式】

第一行一个正整数n，表示小X拥有的一次性空间转移装置的数量。

接下来n行每行两个正整数ai,bi，分别表示该装置可以使他前进ai光年，他拥有bi个该装置。

接下来一行一个正整数m，表示小S制造出的黑洞数目。

接下来一行m个正整数ci，表示黑洞所在的坐标。

【输出格式】

一行一个正整数，表示答案对100000007取模以后的结果。

【样例输入输出】

traveller.in

traveller.out

【样例解释】

1号节点存在黑洞，不能通行。

合法的方式为：先使用装置1，再使用装置2；先使用装置2，再使用装置1。

【数据范围】

对于30%的数据，n≤3，bi≤5，m≤3。

对于另外20%的数据，n≤5，bi≤10，ai≤100。

对于另外10%的数据，m=0。

对于另外10%的数据，ai≤100。

对于100%的数据，n≤6，m≤105，0<ci<∑(bi*ai)，bi≤12，ai≤109。

题解

显然，所有能被访问到的点是很少的，并且还要求方案，显然一些状态是废的。我们可以用状态压缩，用 \(f_{a_1 ... a_n}\) 表示当时每一种推进器用了多少个时的方案。

可以使用set<int>表示不能的到达的点。

转移：\(f_{i,j,k,l,n,m} = f_{i-1,j,k,l,m,n} + f_{i,j-1,k,l,m,n} + f_{i,j,k-1,l,m,n} + f_{i,j,k,l-1,m,n} + f_{i,j,k,l,m-1,n} + f_{i,j,k,l,m,n-1}\) 。

注意到 \(b_i <= 12\) 最多有 13 种方案，可以状态压缩。

代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define MOD 100000007
using namespace std;
long long reflex[5010000];
long long f[5010000];
set <int> t;
int n, m;
long long a[22];
long long b[22];
long long c[110000];
long long p[20];
void DFS(int x, long long tot, long long prefix){
    f[prefix] = tot;
    if (t.find(tot) != t.end()) reflex[prefix] = -1; // banned
    //cout << prefix << ' ' << f[prefix] << ' ' << reflex[prefix] << endl;
    if (x == n+1) return;
    for (int i=0;i<=b[x];i++){
        DFS(x+1, tot+i*a[x], prefix + p[x] * i);
    }
}
int main(){
    freopen("traveller.in","r",stdin);
    freopen("traveller.out","w",stdout);

    p[1] = 1;
    for (int i=2;i<=13;i++)
        p[i] = p[i-1] * 13;
    cin >> n;
    int fin = 0;
    for (int i=1;i<=n;i++)
        cin >> a[i] >> b[i], fin += b[i] * p[i];
//  cout << fin << endl;
    cin >> m;
    for (int i=1;i<=m;i++)
        scanf("%lld", c+i), t.insert(c[i]);
    DFS(1, 0, 0);
    reflex[0] = 1;
    for (int i=1;i<=fin;i++){
        if (reflex[i] != -1)
        for (int j=1;j<=n;j++){
            if (i % p[j+1] / p[j] != 0 && reflex[i - p[j]] != -1)
                reflex[i] = (reflex[i] + reflex[i - p[j]]) % MOD;
        }
    }
    cout << reflex[fin] << endl;
}