Yijan's Blog HomeArchives
10.22 模拟赛

10.22 模拟赛

T1 染色

考虑每个连通块删成一棵树就好了。

mmp场上就我路径压缩写炸。。。。

1
f[1<<21],n,m,t;F(x){t=f[x];return x^t?f[x]=!t?x:F(t):x;}main(s){for(scanf("%*d%d",&s);~scanf("%d%d",&n,&m);f[F(m)]=F(n))s-=F(n)!=F(m);exit(!printf("%d",s));}

T2 乘方

首先，二分答案，变成一个判定问题。

如果只有一个集合，比一个数字小的数字个数就是 $ \sqrt[n]{m} $

然后如果是一些集合交，可以直接把这些集合取 $ lcm $ ，可以证明是对的。

然后可以 $ 2^k $ 枚举子集容斥

当然，这个容斥看起来就可以dp

然后dp就对了，设 $ dp[i][j] $ 表示前 i 个数，LCM为一个 j 的子集的容斥系数

记得开根号二分。。不然T惨

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long
#define MAXN 62
typedef long long ll;
int fuck[MAXN][MAXN];
inline int gcd( int a , int b ) { return b ? gcd( b , a % b ) : a; }
inline int lcm( int x , int y ) { 
if (fuck[x][y]) return fuck[x][y];
return fuck[x][y] = fuck[y][x] = x * y / gcd( x , y ); 
}
int m , k;
int A[MAXN];
int dp[MAXN][MAXN];

inline ll calc(ll n, int k)
{
	ll val = 1;
	for (int i = 0; i < k; i++)
	{
		if ((double)val * n >= 100000000000000000LL)
			return 100000000000000000LL;
		val *= n;
	}
	return val;
}
inline ll sqrt(ll n, int k)
{
	ll res = std::pow(n, 1.0 / k);
	while (calc(res, k) < n)
		res++;
	while (calc(res, k) > n)
		res--;
	return res - 1;
}
int qpow(int x,int y)
{
	int res=1;
	while(y)
	{
		if(y&1)
		{
			if(res*x<=0||res*x>1e17)return -1;
			res*=x;
		}
		y>>=1;
		if(!y)break;
		if(x*x<=0||x*x>1e17)return -1;
		x*=x;
	}
	return res;
}
int lim[MAXN];
int get(int x,int v)
{
	int l=1,r=lim[x],res=1;
	if(x>60)return 1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		int re=qpow(mid,x);
		if(re<=v&&(re!=-1))res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}
inline bool chk( int x ) {
	long long res = 0;
	for( int n = 1 ; n < MAXN ; ++ n )
		res += dp[k][n] * get( n , x ) - dp[k][n];
//	cout << res << endl;
	return res >= m;
}
signed main() {
	lim[2]=1e9;lim[3]=1e6;lim[4]=sqrt(lim[2])+15;lim[5]=4500;lim[6]=2000;
	for(int i=7;i<=60;++i)
	{
		for(int j=1;;++j)
		{
			int now=qpow(j,i);
			if(now==-1)break;
			lim[i]=j;
		}
	}
	int t; cin >> t;
	while( t-- ) {
		scanf("%lld%lld",&m,&k), m--;
		int flag = 0;
		for( int i = 1 ; i <= k ; ++ i ) { scanf("%lld",&A[i]); if( A[i] == 1 ) flag = 1; }
		if( flag ) { cout << m + 1 << endl; continue; }
		memset( dp , 0 , sizeof dp );
		dp[1][A[1]] = 1;
		for( int i = 1 ; i < k ; ++ i ) {
			dp[i + 1][A[i + 1]] = 1;
			for( int n = 1 ; n < MAXN ; ++ n ) if (dp[i][n]) {
				dp[i + 1][n] += dp[i][n];
				if( lcm(n, A[i + 1]) < MAXN )
					dp[i + 1][lcm(n, A[i + 1])] -= dp[i][n];
			}
		}
//		for (int i = 2; i <= 50; i++)
//			cout << dp[k][i][0] - dp[k][i][1] << ' ';
//		cout << endl;
//		chk(64);
		ll l = 1 , r = 100000000000000006LL, ans = -1;
		while( l <= r ) {
			int mid = l + r >> 1;
			if( chk( mid ) ) ans = mid, r = mid - 1;
			else l = mid + 1;
		}
		cout << ans << endl;
	}
}

T3 位运算

and 可以用 这里 的 F 的做法来做，复杂度 $ O(n + v) $ 当然也可以贪心 $ O(nlogv) $

xor 可以用trie直接做

or 不会。貌似只能FWT

所以就粘板子 FWT 跑就行了，直接求位运算卷积就做完了。

当 FWT 板子放在这里把

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
using namespace std;
//#define int long long
typedef long long ll;
#define MAXN 8388610 
#define MAXV 8388610
#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 )
#define upd( a , b ) ( a = ( a + b ) % P )
#define swap( a , b ) a = a ^ b , b = a ^ b , a = a ^ b
#define P 1000000007
int n , q;
int A[MAXN];

namespace fwt {
	
	inline void FWT1(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) 
					a[j + (mid >> 1)] += a[j];
	}
	
	inline void IFWT1(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) 
					a[j + (mid >> 1)] -= a[j];
	}
	
	inline void FWT2(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) 
					a[j] += a[j + (mid >> 1)];
	}
	
	inline void IFWT2(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) 
					a[j] -= a[j + (mid >> 1)];
	}
	
	inline void FWT3(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) {
					ll x = a[j], y = a[j + (mid >> 1)];
					a[j] = x + y, a[j + (mid >> 1)] = x - y;
				}
	}
	
	inline void IFWT3(ll a[], int len) {
		for (int mid = 2; mid <= len; mid <<= 1) 
			for (int i = 0; i < len; i += mid)
				for (int j = i; j < i + (mid >> 1); j++) {
					ll x = a[j], y = a[j + (mid >> 1)];
					a[j] = (x + y) >> 1, a[j + (mid >> 1)] = (x - y) >> 1;
				}
	}
	
	ll a[MAXN], b[MAXN]; int input[400010];
	
	int main() {
		int mx = 0, len = 1; 
		for (int i = 1, x; i <= n; i++) 
			a[A[i]]++, b[A[i]]++, mx = max(mx, A[i]), input[i] = A[i];
		while (len <= mx) len <<= 1;
		if (q == 1) {
			FWT2(a, len);
			for (int i = 0; i < len; i++) a[i] = a[i] * a[i];
			IFWT2(a, len);
			for (int i = len - 1; i >= 0; i--) if (a[i]) {
				ll res = (a[i] - b[i]) >> 1;
				if (res) return printf("%d %lld", i, res), 0;
			}
		} else if (q == 2) {
			bool flag = true;
			for (int i = 2; i <= n; i++) 
				if (input[i] != input[1]) {
					flag = false; break;
				}
			if (flag) return printf("0 %lld", (ll)n * (n + 1) / 2), 0;
			FWT3(a, len);
			for (int i = 0; i < len; i++) a[i] = a[i] * a[i];
			IFWT3(a, len);
			for (int i = len - 1; i >= 0; i--) if (a[i]) 
				return printf("%d %lld", i, a[i] >> 1), 0;
		} else {
			FWT1(a, len);
			for (int i = 0; i < len; i++) a[i] = a[i] * a[i];
			IFWT1(a, len);
			for (int i = len - 1; i >= 0; i--) if (a[i]) {
				ll res = (a[i] - b[i]) >> 1;
				if (res) return printf("%d %lld", i, res), 0;
			}
		}
	}

}


int main() {
    cin >> n >> q;
    int mx = 0;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]) , mx = max(A[i] , mx);
	fwt::main();
	
}
文章作者: yijan
文章链接: https://yijan.co/old11/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog！
比赛FWT