【过题记录】 7.16

A bit common

算法： 组合数学

简要思路：

本题只要求一个序列里面存在一个子序列的AND和为1.
因此我们直接枚举这个子序列即可。
这个子序列里面的数满足这样几个性质：最低位的数字全部是1； 且前面的几位每一位至少有一个0.
直到这两个性质之后我们就可以直接组合数学递推
$\sum C_n^i\ast (2^i-1{)}^{m-1}\ast 2^{(n-i)(m-1)}$

#include<bits/stdc++.h> using namespace std;  #define int long long  const int N = 5e3+100; int n,m,p; int C[N][N];  int Power(int x,int y){ 	int s = 1; 	while (y){ 		if (y&1) s = (s*x)%p; 		x = (x*x)%p; 		y>>=1; 	} 	return s; }  signed main(){ 	cin>>n>>m>>p; 	for (int i = 1; i <= n; i++) C[i][1] = i , C[i][i] = 1; 	for (int i = 1; i <= n; i++) 	  for (int j = 2; j < i; j++) 	    C[i][j] = (C[i-1][j]+C[i-1][j-1])%p;     int aa = 0;     int ans = aa;     for (int i = 3; i <= n; i++){     	int x = C[n][i];     	int y = 0;     	for (int j = 1; j <= i; j++) y = (y+C[i][j])%p;     	y = Power(y,m-1);     	int s1 = x*y%p;     	int z = Power(2,m-1);     	z = Power(z,n-i);     	s1 = s1*z%p;     	ans = (ans+s1)%p; 	} 	cout<<ans; 	return 0; } 

A bit more common

算法：动态规划； 组合数学

简要思路：

此题和上一题的区别就在于这道题要求有两个子序列的AND和为1
上题的答案已经能够保证能够找到一个子序列的AND和为1.
也就是说这题的答案一定是包含在上一题的答案里面的。
我们考虑排除非法的情况。
什么情况非法？ 就是当前子序列的AND和为1，且当前子序列不存在子序列的AND和为1，就是不合法。
也就是说，当前子序列去掉任意一个数，AND和都会大于1
换算到位运算的思维上去说，就是除掉刚刚我们去掉的那个数，当前这一位的二进制位全部都是1
我们称这样的位置为“特殊位”
当前序列是非法的，当且仅当每一个数字都包含有至少一个特殊位。
想要求出所有可能包含特殊位的情况，我们可以用dp去处理
$f[i][j]$表示前i个数字，有j个特殊位的方案数（保证每一个数字都有至少一个特殊位）。
可以如下转移：
$$f[i][j]=i\ast (f[i][j-1]+f[i-1][j-1])$$
当前这一个特殊位，可以分给i个数，去掉当前位，可能有i个数还有特殊位，也可能还有i-1个数有特殊位。

得到f数组之后，就可以枚举所有非法情况：
$$\sum C_n^i\ast 2^{(n-i)(m-1)}\ast \sum C_{m-1}^{t}f[i][t]\ast (2^i-i-1{)}^{m-1-t}$$

而后在把k=1的情况加上即可。（k=1一定非法）

将上一题的答案减去这一题的答案即为总答案。

#include<bits/stdc++.h> using namespace std;   #define ll long long  const int N = 5e3+10;  ll C[N][N],f[N][N]; int n,m; ll p; ll ti[N];  ll Power(ll x,ll y){ 	ll s = 1; 	while (y){ 		if (y&1) s = (s*x)%p; 		x = (x*x)%p; 		y>>=1; 	} 	return s; }  signed main(){ 	cin>>n>>m>>p; 	for (int i = 1; i <= 5000; i++) C[i][1] = i , C[i][i] = 1; 	for (int i = 2; i <= max(n,m); i++) 	  for (int j = 2; j < i; j++) 	    C[i][j] = (C[i-1][j]+C[i-1][j-1])%p; 	     	for (int i = 0; i <= 5000; i++) ti[i] = Power(2,i*1ll);     ll anss = 0;     for (int i = 1; i <= n; i++){     	ll x = C[n][i];     	ll y = 0;     	y = ti[i];     	y = (y-1+p)%p;     	y = Power(y,m-1);     	ll s1 = x*y%p;     	ll z = ti[m-1];     	z = Power(z,n-i);     	s1 = s1*z%p;     	anss = (anss+s1)%p; 	} 	f[0][0] = 1; 	for (int i = 1; i <= n; i++) 	  for (int j = i; j <= m; j++) 	    f[i][j] = i*(f[i-1][j-1]+f[i][j-1])%p; 	ll ans = 0; 	for (int i = 2; i <= n; i++){ 		ll s1 = C[n][i]; 		ll s2 = ti[n-i]; s2 = Power(s2,m-1); 		ll S = 0; 		for (int t = i; t <= m-1; t++){ 			ll a = C[m-1][t]; 			a = a*f[i][t]%p; 			ll b = ti[i]; 			b = (b-(i+1)+p)%p; 			b = Power(b,m-1-t); 			a = a*b%p; 			S = (S+a)%p; 		} 		S = S*s1%p; S = S*s2%p; 		ans = (ans+S)%p; 	} 	ll le = Power(2,m-1); le = Power(le,n-1); le = le*n%p; 	ans = (ans+le)%p; 	ans = (anss-ans+p)%p; 	cout<<ans<<endl; 	return 0; } 

World finals

简要思路：

分别将一场的选手移到另一场取个max即可

#include<bits/stdc++.h> using namespace std; struct st{ 	string name; 	int t,x; }a[100010],b[100010]; map<string,int> mp; int n,m,s1,s2,jsq1,jsq2,ans; int main(){ 	scanf("%d",&n); 	for (int i=1;i<=n;i++){ 		cin>>a[i].name; 		scanf("%d%d",&a[i].t,&a[i].x);  		if (a[i].name=="lzr010506")s1=i; 		mp[a[i].name]++; 	} 	scanf("%d",&m); 	for (int i=1;i<=m;i++){ 		cin>>b[i].name; 		scanf("%d%d",&b[i].t,&b[i].x); 		if (b[i].name=="lzr010506")s2=i; 		mp[b[i].name]++; 	} 	ans=1e9; 	if (s1){ 		for (int i=1;i<=n;i++){ 			if (i==s1||mp[a[i].name]==2)continue; 			if (a[i].t>a[s1].t)jsq1++; 			if (a[i].t==a[s1].t&&a[i].x<a[s1].x)jsq1++; 		} 		ans=min(ans,jsq1); 	} 	if (s2){ 		for (int i=1;i<=m;i++){ 			if (i==s2||mp[b[i].name]==2)continue; 			if (b[i].t>b[s2].t)jsq2++; 			if (b[i].t==b[s2].t&&b[i].x<b[s2].x)jsq2++; 		} 		ans=min(ans,jsq2); 	} 	printf("%d",ans+1); 	return 0; }