【补题】Codeforces 1033 : Lyft Level 5 Challenge 2018 - Elimination Round （ABCDF）

前言

又是发布失败，全部清空，重写一遍。
再这样一次，我就不用csdn了。

When everything’s lost they pick up their hearts and avenge defeat.
League of Legends - Legends Never Die

总结

1. java.math.BigInteger.isProbablePrime(int)可以判断给定的概率下是否是素数，参数越大耗时越多，也越准确。
2. 与序列有关的题目要分清楚变量表示的是值还是下标。
3. 分解质因数，求gcd时要考虑是否相等。
4. 二进制的二输入门都可以转换成三进制下的加法来快速预处理结果。（tql）
5. 十进制的二进制表示在三进制下反转十进制
   for(int i=1;i<W;++i) ttt[i] = ttt[i/2]*3+i%2;

A. King Escape 水

国王和目标点必须在以皇后为原点的坐标系中的同一象限。

(bx-ax)*(cx-ax)>0 && (by-ay)*(cy-ay)>0

B. Square Difference 数学

求$a^2-b^2$a2−b2是否为素数。(1<=b<a<=1e11)

当$a-b==1且a+b$a−b==1且a+b为素数时，原数为素数，$O(√n)$O(√n)判断即可。
附一个java的神仙写法：

// LittleFall : Hello!
import java.util.*;
import java.math.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int xt = 0; xt < t; ++xt)
        {
            BigInteger a = sc.nextBigInteger(), b = sc.nextBigInteger();
            a = a.multiply(a).subtract(b.multiply(b));
            System.out.println(a.isProbablePrime(20)?"YES":"NO");
        }
    }
}

C. Permutation Game 博弈

给定排列P。Alice和Bob玩游戏，初始时弹珠在位置x上，如果存在一个位置y使得$P[y]&gt;p[x]且|y-x| \% P[x]==0$P[y]>p[x]且∣y−x∣%P[x]==0，那么玩家可以把弹珠移到位置y上。轮流操作，Alice先手，两人绝顶聪明，最先不能操作的人输，问每个初始位置时谁赢？

如果一个状态能转移到必败态，那么它是必胜态，否则是必败态。

n为必败态，从n-1到1依次检查即可，由调和级数求和公式，复杂度$O(nlogn)$O(nlogn).
序列题一定要分清楚变量表示值还是下标。

int save[M]; //序列
int id[M]; //每个数在序列中的位置
int tag[M]; //tag[i]表示序列中第i个位置必胜还是必败1/2
int main(void)
{
	int n = read();
	for(int i=1;i<=n;++i)
	{
		save[i]=read();
		id[save[i]] = i;
	}
	for(int num=n;num;--num)
	{
		int nxt = id[num]%num; //位置
		for(;nxt<=n;nxt+=num) 
			if(save[nxt]>num && tag[nxt]==2)
				tag[id[num]]=1;
		if(tag[id[num]]!=1)
			tag[id[num]]=2;
	}
	for(int i=1;i<=n;i++)
		putchar(tag[i]==1?'A':'B');

    return 0;
}

D. Divisors 数学

给出n(500)个因数只有3到5个的数(1e18)，求它们积的因数个数。

唯一分解定理：

如果知道了最后数字的各个质因数个数，那么就可以快速地求出因数个数。
由唯一分解定理

• 因数个数为3：2*2
• 因数个数为4：2*2*2，2*3
• 因数个数为5：2*2*2*2

首先可以用二分或者其他方法判断数字是否是质数的4,3,2次幂（注意先判4次再判2次），将质数记录下来。
剩下的数全部是两个质数的乘积，用已知的质数去试除这些数，将新得到的质因子也记录下来。
对所有不相等的两质数乘积两两求gcd，又可以得到若干质数。

对所有的数字拿这些质数去分解，记录这些质数出现了多少次。
还剩下的数字就是由没有出现过的质数组合而成。

使用唯一分解定理组合即得到答案。

/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; using ll = long long; inline ll read();
const int M = 500016, MOD = 998244353;

ll save[M];
int tag[M];
map<ll,int> mp;
ll sqr(ll num, ll p)
{
	ll l=1,r;
	if(p==2) r=2*MOD;
	else if(p==3) r=1500000;
	else if(p==4) r=40000;

	while(l<=r)
	{
		ll mid = (l+r)>>1;
		ll tmp=1;
		for(int i=0;i<p;i++)
			tmp *= mid;
		if(tmp==num) return mid;
		else if(tmp<num) l=mid+1;
		else if(tmp>num) r=mid-1;
	}
	return -1;
}
int main(void)
{
	int n = read();
	for(int i=0;i<n;++i) save[i] = read();

	//第一次扫描,开4/3/2次根号,如果成功则标记1
	for(int i=0;i<n;++i)
	{
		for(int p=4;p>=2;--p)
		{
			ll tmp = sqr(save[i], p);
			if(tmp!=-1)
			{
				printf("? p=%d\n",p );
				mp[tmp] = 0;
				tag[i] = 1;
				break;
			}
		}
	}
	//第二次扫描,使用已知素数进行检测
	for(int i=0;i<n;i++) if(tag[i]!=1)
		for(auto x : mp)
			if(save[i] % x.first==0)
				mp[save[i]/x.first]=0, tag[i]=2;
	//第三次扫描,两两之间尝试求gcd
	for(int i=0;i<n;++i) if(tag[i]!=1)
		for(int j=i+1;j<n;++j) if(tag[j]!=1 && save[i]!=save[j])
		{
			ll x = __gcd(save[i],save[j]);
			if(x!=1)
			{
				mp[x] = 0;
				mp[save[i]/x]=0;
				mp[save[j]/x]=0;
				tag[i]=2;
				tag[j]=2;
			}
		}
	//第四次扫描,找到剩下的独立素数个数
	map<ll,int> subs;
	for(int i=0;i<n;++i)
		if(tag[i]==0)
			subs[save[i]]++;
	//mp.erase(1);
	//第五次扫描,得出各素因数个数
	for(int i=0;i<n;++i)
		for(auto &x : mp)
			while(save[i] % x.first==0)
			{
				save[i]/=x.first;
				x.second++;
			}
	ll ans = 1;
	for(auto x:mp)
	{
		//printf("%I64d %d\n",x.first,x.second );
		ans = ans * (x.second+1) % MOD;
	}
	for(auto x:subs)
	{
		//printf("%I64d %d\n",x.first,x.second );
		ans = ans * (x.second+1) % MOD;
		ans = ans * (x.second+1) % MOD;
	}
	cout << ans << endl;

    return 0;
}

F. Boolean Computer 二进制操作，dfs

给出n(30000)个w(12)位的数，和m(50000)个w位的二进制门，每个w位的二进制门由w个与、或、异或、与非、或非、同或之中的门组成。对每个w位的二进制门，问有几对数输入能使得输出为0.

我的想法（和题解的第二种做法类似）：
最多有4096种数，对每个门遍历每种数，查询符合要求的数有多少个。
这个要求类似于：某些位为1，某些位为0，某些位什么都可以。
最多有3^12种条件，且每个数都满足2^12个条件，所以可以提前预处理。
因为一些奇怪的原因，存储时使用了4进制。
$预处理2^w个数，每个2^w，查询m*2^w，得到要求需要w$预处理2w个数，每个2w，查询m∗2w，得到要求需要w
$总时间复杂度O(4^w+m*w*2^w)，空间复杂度O(4^w)$总时间复杂度O(4w+m∗w∗2w)，空间复杂度O(4w)。

/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; using ll = long long; inline int read();
const int M = 4096, MOD = 1000000007;

int save[M];//存放数字
int table[M*M]; //放表(4^12,可优化到3^12) //0表示强制0,1表示强制1,2表示无所谓

void dfs(int num, int lst, int amount) //lst表示下一个可置2的位置
{
	table[num]+=amount;
	if(lst<0) return;
	for(int ch = lst;ch>=0;--ch)
	{
		int nxt = num;
		nxt &= ~(1<<(ch*2)); //将第lst*2位置0
		nxt |= 1<<(ch*2+1); //将第lst*2+1位置1
		dfs(nxt,ch-1,amount);
	}
}
int need[200][2];
int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt","r",stdin);
    #endif

	int w = read(), n = read(), m = read();
	int W = 1<<w;
	for(int i=0;i<n;++i)
		++save[read()];
	for(int num=0;num<W;++num) if(save[num])
	{
		//拉宽
		int need = 0;
		for(int bit=0;bit<w;++bit)
			if((num>>bit)&1)
				need += (1<<(bit<<1));
		//printf("num=%d need=%d\n",num,need );
		//置2
		dfs(need, w-1, save[num]);
	}
	//for(int i=0;i<W*W;i++)
	//	printf("%d %d\n",i,table[i] );
	//0表示强制0, 1表示强制1, 2表示都行, 3表示都不行
	need['A'][0] = 2; need['A'][1] = 0;
	need['O'][0] = 0; need['O'][1] = 3;
	need['X'][0] = 0; need['X'][1] = 1;
	need['a'][0] = 3; need['a'][1] = 1;
	need['o'][0] = 1; need['o'][1] = 2;
	need['x'][0] = 1; need['x'][1] = 0;
	char tmp[20]; 
	for(int _m=0;_m<m;++_m)
	{
		int ans = 0;
		scanf("%s",tmp);
		for(int num=0;num<W;++num) if(save[num])
		{
			int want = 0;
			for(int bit=0;bit<w;bit++)
			{
				int c = need[(int)tmp[w-bit-1]][(num>>bit)&1];
				if(c==3)
				{
					want=-1;
					break;
				}
				want |= c << (bit<<1);
			}
			//printf("num=%d want=%d\n",num,want );
			if(want!=-1)
				ans += save[num]*table[want];
		}
		printf("%d\n",ans );
	}
    return 0;
}

题解的第一种做法：
如果把二进制的表示放在三进制下相加，不会产生进位且由每一位的结果(0,1,2)可以确定6个位操作的答案。
把所有的加法结果都预处理出来，然后对每个w位的二进制门dfs查询符合条件的操作即可。
$总时间复杂度O(4^w+m*2^w)$总时间复杂度O(4w+m∗2w)，预处理似乎可以用FFT降到$O(w*3^w)$O(w∗3w)，但是常数会很大。

/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; using ll = long long; inline int read();
const int M = 4096, MOD = 1000000007;

int save[M], ttt[M], table[531441];
int dfs(char*op, int t) //当前操作, 答案位置
{
	if(!*op) return table[t];
	t*=3;
	switch(*op++)
	{
		case 'A': return dfs(op,t)+dfs(op,t+1);
		case 'O': return dfs(op,t);
		case 'X': return dfs(op,t)+dfs(op,t+2);
		case 'a': return dfs(op,t+2);
		case 'o': return dfs(op,t+1)+dfs(op,t+2);
	}
	return dfs(op,t+1); //x
}
int main(void)
{
	int w = read(), n=read(), m=read(), W=1<<w;
	for(int i=1;i<W;++i)
		ttt[i] = ttt[i/2]*3+i%2;
	while(n--) ++save[read()];
	for(int i=0;i<M;++i) if(save[i])
		for(int j=0;j<M;++j) if(save[j])
			table[ttt[i]+ttt[j]] += save[i]*save[j];
	char str[10];
	while(m--)
	{
		scanf("%s",str);
		printf("%d\n",dfs(str,0) );
	}

    return 0;
}


inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

学到了十进制的二进制表示在三进制下反转十进制的巫毒操作，虽然原理还不太懂：

for(int i=1;i<W;++i) ttt[i] = ttt[i/2]*3+i%2;