题意

有nn个站点，排成圆形，每站间距mm，现从0点出发，提供tt个油箱，问：拿走若干个油箱可以让出发者无法到达任意一个站点，这样的方案有多少？（出发者可以顺时针走，也可以逆时针走）数据规模分别为：2 ≤ n ≤ 1000,1 ≤ m ≤ 120,1 ≤ t ≤ 100002 ≤ n ≤ 1000,1 ≤ m ≤ 120,1 ≤ t ≤ 10000

分析

本题想了好几天，看了若干个题解：

• 许昊然julao的codeforces解题报告
• 一份AC代码，不知道哪个julao写的

一并表示谢意。

首先要注意到几个个有趣的事实：对于一个容量vivi的油箱，它的作用与vi%mvi%m等效。因为题目并不要求你到达第几个站点，它只想你达不到；另外，每个容量只能带一个，不然出发者显然可以原路返回；而类似地，vivi同m−vim−vi等效。

因此，题目的规模轻易的可以降到260260。这样就可以考虑状态压缩了。设状态保存在b（bitset）中，记bibi为真时，油量为i的油箱不可以使用（最后的解利用乘法原理计算）。那么，第j个被使用时，b转化为b|b>>>k|b<<<kb|b>>>k|b<<<k（即循环左移/循环右移）。简单说下为什么要右移：若原来第i个状态真，那么说明变为i时可以到达。那么现在必须让他达不到油箱容量i+k，才能使得出发者仍旧不能到达。

最终题目得解。

代码

#include 
    
     #define MP make_pair#define PB push_back#define fi first#define se second#define ZERO(x) memset((x), 0, sizeof(x))#define ALL(x) (x).begin(),(x).end()#define rep(i, a, b) for (int i = (a); i <= (b); ++i)#define per(i, a, b) for (int i = (a); i >= (b); --i)#define QUICKIO                  \    ios::sync_with_stdio(false); \    cin.tie(0);                  \    cout.tie(0);using namespace std;using ll = long long;using ull = unsigned long long;using pi = pair
     
      ;using pii = pair
      
       ;const int MAXN=125;using bst = bitset
       
        ;#define NDEBUGtemplate
        
         T read(){    T tmp; cin>>tmp;    return tmp;}ll ans=0,mod=1000000007;int n,m,k;int cnt[MAXN];inline bst mv(bst& x,int val,bool opt,int sz=m){    if(opt) // left    {        return (x<
         
          >(sz-val)); } else // right { return (x>>val)|(x<<(sz-val)); }}void dfs(bst nb,int n,ll mulv){ ans=(ans+mulv)%mod; rep(i,n,m/2) { if(cnt[i] && !nb[i] && !nb[m-i]) { dfs(nb|mv(nb,i,true)|mv(nb,i,false),i+1,mulv*cnt[i]%mod); } }}int main(){QUICKIO //cin>>n>>m>>k; scanf("%d%d%d",&n,&m,&k); ZERO(cnt); rep(i,0,k-1) { //int tmp=read
          
           ()%m; int tmp; scanf("%d",&tmp); tmp%=m; cnt[min(tmp,m-tmp)]++; } bst tmp=1; dfs(tmp,0,1); printf("%d\n",int(ans%mod)); //cout<
           
            <