Sums gym100753M

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

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

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

u + x < Mod

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

Sums gym100753M

最新文章

热门文章