6.11 模拟赛

A Game

我们考虑所有人的初始情况是一样的，所以可以逐一确定每个人的做任务情况。

所以有了一个朴素的想法，我们设 $dp[i][j]$ 表示前 $i$ 个人，一共已经做了 $j$ 个任务，这种情况下最小的天数是多少。不难发现，如果我们可以算出 $f(k-j,t)$ 表示一共 $k-j$ 的体力值，一共用 $t$ 天最多做多少任务的话，就可以直接 $O(nm^2)$ 解决问题。

这个东西看起来需要一个 $O(km^2)$ 的转移，但是事实上我们可以算出 $pd[i][j]$ 表示 $i$ 天做了 $j$ 个任务最少需要的体力值，然后会发现其实之需要枚举到 $\sqrt k$ 来转移，于是复杂度就是 $m^2\sqrt k$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep( i , a , b ) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per( i , a , b ) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all( x ) (x).begin(), (x).end()
#define mem( a ) memset(a, 0, sizeof a)
typedef long long ll;
const int P = 998244353;
int n , m , k;
int dp[52][1006] , pd[1006][1006] , f[1006][1006];

void ckm( int& a , int b ) {
	a = max( a , b );
}

void solve( ) {
	cin >> n >> m >> k;
	if( k < m ) { puts("-1"); return; }
	if( k >= m * m ) { puts("1"); return; }
	memset( pd , 0x3f , sizeof pd );
	pd[0][0] = 0;
	for( int i = 1 ; i * i <= k ; ++ i ) {
		int w = i * i;
		rep( j , 1 , m ) rep( t , i , m ) {
			pd[j][t] = min( pd[j][t] , pd[j - 1][t - i] + w );
		}
	}
	rep( j , 1 , m ) {
		per( t , m , 1 ) if( pd[j][t] <= k ) {
			ckm( f[j][max( 0 , pd[j][t] - ( k - m ) )] , t );
		}
		rep( t , 1 , m ) ckm( f[j][t] , f[j][t - 1] );
	}
	memset( dp , 0x3f , sizeof dp );
	dp[0][0] = 0;
	rep( i , 0 , n - 1 ) rep( j , 0 , m ) {
		rep( t , 1 , m ) {
			int tr = min( m , j + f[t][k - j - ( k - m )] );
			dp[i + 1][tr] = min( dp[i + 1][tr] , dp[i][j] + t );
		}
		dp[i + 1][j] = min( dp[i + 1][j] , dp[i][j] );
	}
	printf("%d\n",dp[n][m]);
}


signed main( ) {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	//    int T;cin >> T;while( T-- ) solve();
	solve( );
}

B Matrix

这题让我学习了一个新的数据结构，我另外开一篇文章写吧 QAQ

C Counting

对于 $m = 0$ 的情况，可以直接应用上一次的 $dp$ ，具体来说我们枚举第一个有数脱离限制的位是谁，在这个位的下面一定可以通过填这个数来达成任意数，然后再通过 $dp$ 算出这一位是 $0 / 1$ 的方案数量。这个问题可以 $O(n\log v)$ 解决。

首先考虑容斥，可以容斥后就是钦定一些边，条件变成边两边必须相等。如果我们可以枚举边集的子集，那么最后就会形成若干个联通块，而每个联通块的限制就是相等且小于等于最小值。然后可以发现，如果一个联通块大小是偶数，那么它就没用了，因为它怎么取值都会异或出 $0$ ，但是别忘了最后需要给方案数量乘上这个联通块的最小值加一。对于奇的联通块，我们只需要把最小值的位置找出来，然后对这些最小值做一个 $dp$ 即可。这样做复杂度和 $2^m$ 有关，必然是不行的。

我们考虑可以算出如果选择一个子集作为一个联通块，它的容斥系数是多少。这就是选择 $k$ 条边，然后这些边使得这个联通块联通，对于所有这种情况算出 $-1$ 的边数次方和。我们设 $f(S)$ 为一个集合的这个值，那么这个东西可以类似联通图计数的计算，具体来说选择一个点，然后枚举它所在的联通块。有：

$$f(S) = [\text{no edge in } S] - \sum_{T \sub S \setminus \{u\}} f(T)$$

这里的 $\text{no edge in } S$ 来自于二项式定理，对所有子集算 $(-1)$ 的大小次方和在集合有边的情况下一定是 $0$ 。这个直接暴力算就是 $O(3^n)$ 的。

然后就可以 $O(bell(n))$ 来做这个题了，如果枚举的时候只枚举奇联通块然后最后考虑偶联通块甚至可以跑过 $n = 15$ 。

我们考虑怎么优化。我们可以设 $dp[S][T]$ ，其中 $S$ 集合中的数就是所有之前选择的奇联通块的最小值的集合，然后 $T$ 就是剩下的还可以选择到某个集合的数的集合。每次转移就是枚举 $T$ 的一个子集作为一个新的集合加入。这样做复杂度是 $O(4^n \times poly(n))$ 的。无法通过本题。

于是我们考虑按照最小值从小到大来枚举加入的集合。具体来说，我们把 $dp$ 状态记录为 $dp[S \or T][k]$ ，其中我们定一个界限 $k$ ，前面那个集合中小于等于 $A[k]$ 的位置如果有小于等于 $A[k]$ 的位置，这些位置作为 $S$ 集合，剩下的位置如果有值就是 $T$ 集合的数。于是转移就是枚举一个 $T$ 的子集，这个子集必须包含 $T$ 中的最小值，然后把这个集合加入 $S$ 。具体来说，如果这个集合大小是偶数，那么乘一个系数，并不需要往 $S$ 加入数，如果是奇数，那么把最小值加入 $S$ 。最后都需要把数在 $T$ 集合删掉。

这样乍一看是 $O(3^n n)$ 的，事实上考虑真正的状态数，对于每个 $k$ 我们之需要对后 $2^{n-k}$ 枚举子集，那么对于一个固定的数来说，相当于它二进制下的每个后缀都需要被枚举子集一次，那么我们把每个后缀长度拿出来分别看，复杂度其实是 $3^n + 3^{n-1} + \cdots +3^0 = O(3^n)$ 。于是这题总复杂度 $O(3^n)$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "unordered_map"
#include "assert.h"
#include "set"
#include "queue"
using namespace std;
#define MAXN 19
//#define int long long
#define rep( i , a , b ) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per( i , a , b ) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all( x ) (x).begin(), (x).end()
#define mem( a ) memset(a, 0, sizeof a)
typedef long long ll;
typedef double db;
const int P = 998244353;
int n , m;
ll C;
ll A[MAXN];
pair<ll,int> a[MAXN];
int G[MAXN][MAXN];
int dp[1 << 18 | 6][19] , f[1 << 18 | 6] , ed[1 << 18 | 6] , idx[MAXN] , mnp[1 << 18 | 6];
int pd[MAXN][2];

void Inc( int& a , int b ) {
	a = ( a + b < P ? a + b : a + b - P );
}

int ipw[666];

void solve( ) {
	cin >> n >> m >> C;
	rep( i , 1 , n ) scanf("%lld",A + i) , a[i] = mp( A[i] , i ) , idx[i] = i;
	sort( idx + 1 , idx + 1 + n , []( int o , int b ) { return a[o] < a[b]; } );
	ipw[0] = 1;
	rep( i , 1 , 60 ) ipw[i] = ipw[i - 1] * 1ll * ( P + 1 >> 1 ) % P;
	rep( i , 1 , m ) {
		int u , v;
		scanf("%d%d",&u,&v);
		G[u][v] = G[v][u] = 1;
	}
	rep( i ,  1 , ( 1 << n ) - 1 ) {
		rep( u , 1 , n ) if( i & ( 1 << u - 1 ) ) rep( v , 1 , n ) if( i & ( 1 << v - 1 ) ) if( G[u][v] )
							ed[i] = 1;
		mnp[i] = 0;
		rep( u , 1 , n ) if( i & ( 1 << u - 1 ) ) {
				if( !mnp[i] || a[mnp[i]] > a[u] ) mnp[i] = u;
			}
	}
	f[0] = 1;
	rep( s , 1 , ( 1 << n ) - 1 ) {
		int x = ( s & -s ) , t = s ^ x;
		f[s] = !ed[s];
		if( !t ) continue;
		for( int e = ( t - 1 ) & t ; ; e = ( e - 1 ) & t ) {
			if( !ed[s ^ e ^ x] ) Inc( f[s] , P - f[e ^ x] );
			if( !e ) break;
		}
	}
	dp[( 1 << n ) - 1][0] = 1;
	per( s , ( 1 << n ) - 1 , 1 ) {
		rep( tt , 0 , n - 1 ) if( dp[s][idx[tt]] ) {
			int k = idx[tt];
			int t = 0;
			rep( p , 1 , n ) if( ( s & ( 1 << p - 1 ) ) && a[p] > a[k] )
					t |= ( 1 << p - 1 );
			if( !t ) continue;
			int d = 1 << mnp[t] - 1;
			for( int x = ( t ^ d ) ; ; x = ( x - 1 ) & ( t ^ d ) ) {
				if( ~__builtin_popcount( x ) & 1 ) Inc( dp[s ^ x][mnp[t]] , dp[s][k] * 1ll * f[x ^ d] % P );
				else Inc( dp[s ^ x ^ d][mnp[t]] , dp[s][k] * 1ll * f[x ^ d] % P * ( ( A[mnp[x ^ d]] + 1 ) % P ) % P );
				if( !x ) break;
			}
		}
	}
	int as = 0;
	rep( s , 1 , ( 1 << n ) - 1 ) rep( k , 1 , n ) if( dp[s][k] ) {
			int flg = 0;
			rep( i , 1 , n ) if( ( s & ( 1 << i - 1 ) ) && a[i] > a[k] ) {
					flg = 1; break;
				}
			if( !flg ) {
				vector<ll> pr;
				ll xr = 0;
				rep( i , 1 , n ) if( s & ( 1 << i - 1 ) ) {
						pr.pb( A[i] );
						xr ^= A[i];
					}
				int res = 0;
				per( d , 60 , 0 ) {
					if( ( xr >> d + 1 << d + 1 ) != ( C >> d + 1 << d + 1 ) ) break;
					int val = 1;
					mem( pd );
					pd[0][0] = 1;
					rep( i , 1 , pr.size() ) {
						rep( t , 0 , 1 ) {
							if( ( pr[i - 1] >> d ) & 1 ) {
								pd[i][t ^ 1] = ( pd[i][t ^ 1] + ( ( pr[i - 1] & ( 1ll << d ) - 1 ) + 1 ) % P * pd[i - 1][t] % P ) % P;
								pd[i][t] = ( 1ll * pd[i][t] + ( 1ll << d ) % P * pd[i - 1][t] ) % P;
							} else {
								pd[i][t] = ( 1ll * pd[i][t] + ( ( pr[i - 1] & ( 1ll << d ) - 1 ) + 1 ) % P * pd[i - 1][t] ) % P;
							}
						}
						val = ( ( pr[i - 1] & ( 1ll << d ) - 1 ) + 1 ) % P * 1ll * val % P;
					}
					if( C & ( 1ll << d ) ) {
						res = ( res + ( ( pd[pr.size()][1] + ( ( xr & ( 1ll << d ) ) ? P - val : 0 ) ) * 1ll * ipw[d] % P ) ) % P;
					} else {
						res = ( res + ( ( pd[pr.size()][0] + ( ( ~xr & ( 1ll << d ) ) ? P - val : 0 ) ) * 1ll * ipw[d] % P ) ) % P;
					}
				}
				if( xr == C ) ++ res;
//				printf("%d %d %d ",s,k,dp[s][k]); for( auto x : pr ) printf("%lld ",x); printf(" : %d\n",res);
				as = ( as + res * 1ll * dp[s][k] ) % P;
			}
		}
	cout << as << endl;
}


signed main( ) {
	freopen("counting.in", "r", stdin);
	freopen("counting.out", "w", stdout);
	//    int T;cin >> T;while( T-- ) solve();
	solve( );
}