UOJ310

【题意】

给出N（(N leq 10^6)）个数字，两个人来选。每一个人各选出一个数字（(S leq 10^6)）集合（集合不能相交）。问两个人取的数字的异或和正好相等的方案数（模一个NTT质数）。

【做法】

先试着暴力用FWT来表示，然后优化这一过程，发现另一个形式的FWT>_<。

hdu5870

【题意】

给出一个(N)个点、(M)条边的简单无向图。再给定一个常数(X)。对于一个无序对((x,y))，如果存在一个正数(z)，使得添加了(x-y)，长度为(z)的边后，原图仍然没有重边，且从(1)到 (N)的最短路路径数增加量 > X ，那么称其为合法的。求合法的((x,y))组数。 (N leq 20000) , $ M leq 10^5 $, $ X leq 10^9 $

【做法】

感觉这题挺不错。首先假设暴力枚举两个点x和y，判断在它们之间连边是否合法。我们不妨设(f_x)为从1到x的走最短路方案数,(g_y)表示从y到n的走最短路方案数，那么增加的方案数显然为(f_x*g_y)（注意x和y不必一定在原图的最短路上）；同时我们必须保证(dist_{1,x}+dist{y,n}<dist{1,n})。根据上面的式子，我们可以按dist重新编号点，每次枚举y后，对应前缀的一段x合法。判断 (f_x*g_y) > X 时，可以用可持久化线段树计算合法的x数量（也可以离线）。效率是(O(N log N))