Sums gym100753M

同余最短路模板，然而这个东西貌似也可以做去年D1T2

首先我们选择一个模数作为基准，然后剩下的这样连边：

对于一个面值为 x 的硬币 ，当前在 u 这个点（感性理解一下吧）

1. u + x < Mod

   这种情况直接从u向 u + x 连一条长度为0的边，表示我们在 0 * M + (u + x) 的时候就已经可以凑出了

2. u + x > Mod

   这种情况下可以 u 向 ( u + x ) mod Mod 连一条长度为1的边，表示通过x的硬币至少在 1 * M + ( u + x ) 凑出。

直接dijk 复杂度会炸（但是可以用zkw线段树优化成 nlogm，就爆过去了）

然后如果Mod取硬币面值的最大值，那么这就是个01bfs，但是复杂度也是 O(n + M) 然而M是 n^2级别的

我们发现每个点只会考虑一次，所以我们可以用bitset优化这个bfs。具体而言，如果我们把 $ a[i] $ 存到一个bitset中，我们需要的转移是 $ trans $ 集体往左移动u次且循环移位后的trans。

学到了Bitset优化搜索这个套路233 但是由于需要提取1，还是得手写。。

这样优化就是 $ n + \frac{M}{w} $ 了

为了偷懒还是用类似dijk的bfs吧。。反正复杂度没问题

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
//#define int long long
typedef long long ll;
#define MAXN 50006 
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
#define cmx( a , b ) a = max( a , b )
#define cmn( a , b ) a = min( a , b )
void read( int& x ) {
    scanf("%d",&x);
}
void read( ll& x ) {
    scanf("%lld",&x);
}
int n , q;
int A[MAXN] , mx;

struct Bitset
{
    unsigned a[1600];
    void reset()
    {
        memset(a,0,sizeof(a));
    }
    Bitset()
    {
        reset();
    }
    void flip(int x)
    {
        a[x>>5]^=1<<(x&31);
    }
    void set(int x)
    {
        a[x>>5]|=1<<(x&31);
    }
    void reset(int x)
    {
        a[x>>5]&=~(1<<(x&31));
    }
    int test(int x)
    {
        return (a[x>>5]>>(x&31))&1;
    }
    Bitset operator ~()const
    {
        Bitset ret;
        for(int i=0;i<1600;i++)ret.a[i]=~a[i];
        return ret;
    }
    Bitset operator &(const Bitset &b)const
    {
        Bitset ret;
        for(int i=0;i<1600;i++)ret.a[i]=a[i]&b.a[i];
        return ret;
    }
    Bitset operator |(const Bitset &b)const
    {
        Bitset ret;
        for(int i=0;i<1600;i++)ret.a[i]=a[i]|b.a[i];
        return ret;
    }
    Bitset operator ^(const Bitset &b)const
    {
        Bitset ret;
        for(int i=0;i<1600;i++)ret.a[i]=a[i]^b.a[i];
        return ret;
    }
    Bitset operator <<(const int t)const
    {
        Bitset ret;
        unsigned last=0;
        int high=t>>5,low=t&31;
        for(int i=0;i+high<1600;i++)
        {
            ret.a[i+high]=last|(a[i]<<low);
            if(low)last=a[i]>>(32-low);
        }
        return ret;
    }
    Bitset operator >>(const int t)const
    {
        Bitset ret;
        unsigned last=0;
        int high=t>>5,low=t&31;
        for(int i=1600-1;i>=high;i--)
        {
            ret.a[i-high]=last|(a[i]>>low);
            if(low)last=a[i]<<(32-low);
        }
        return ret;
    }
    vector<int> ones()const
    {
        vector<int> ret;
        for(int i=0;i<1600;i++)
        {
            unsigned tmp=a[i];
            while(tmp)
            {
                short t=__builtin_ctz(tmp);
                ret.pb((i<<5)|t);
                tmp^=1u<<t;
            }
        }
        return ret;
    }
}use,trans;
int dis[MAXN];
priority_queue< pii , vector<pii> , greater<pii> > Q;
vector<int> cur;
void bfs(  ) {
    memset( dis , 0x3f , sizeof dis );
    Q.push( mp( 0 , 0 ) ); dis[0] = 0;
    while( !Q.empty() ) {
        int u = Q.top().se; Q.pop( );
        cur = ( ( ( trans << u ) | ( trans >> ( mx - u ) ) ) & use ).ones( );
        for( auto& v : cur ) {
            if( v < u ) 
                dis[v] = dis[u] + 1 , Q.push( mp( dis[v] , v ) ) , use.reset( v );
            else 
                dis[v] = dis[u] , Q.push( mp( dis[v] , v ) ) , use.reset( v );
        }
    }
}

int main() {
    read( n );
    for( int i = 1 ; i <= n ; ++ i ) 
        read( A[i] ) , mx = max( mx , A[i] );
    for( int i = 1 ; i <= n ; ++ i ) trans.set( A[i] );
    for( int i = 0 ; i <= mx ; ++ i ) use.set( i );
    bfs();
    read( q );
    int x;
    while( q --> 0 ) {
        read( x );
        int a = x % mx , b = x / mx;
        puts( ( dis[a] == 0x3f3f3f3f || dis[a] > b ) ? "NIE" : "TAK" );
    }
}

/*
 * Things you should pay attention to
 * inf is big enough?
 * out of bounds?
 * long long ?
 */

Sums gym100753M

原文：https://www.cnblogs.com/yijan/p/gym100753m.html