ABC150 C-F

C

\(N \le 8\)，全排列即可。实现时可以使用 next_permutation。当然用康拓展开也没有问题。

以下代码时间复杂度 \(O(n!)\)。

#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>using namespace std;int n,a[1001],b[1001],c[1001],x,y,cnt;bool cka( void )
{for( int i = 1 ; i <= n ; i ++ )if( a[i] != c[i] )return false;return true;
}bool ckb( void )
{for( int i = 1 ; i <= n ; i ++ )if( b[i] != c[i] )return false;return true;
}int main()
{cin >> n;for( int i = 1 ; i <= n ; i ++ )cin >> a[i],c[i] = i;for( int i = 1 ; i <= n ; i ++ )cin >> b[i];do{cnt ++;if( cka() ) x = cnt;if( ckb() ) y = cnt;}while( next_permutation( c + 1 , c + n + 1 ) );if( x > y ) swap( x , y );cout << y - x;return 0;
}

D

考虑求出最小的 \(X\)。有了这个 \(X\) 后，答案显然为 \(\lceil \dfrac{ \lfloor \dfrac{M}{X} \rfloor }{2} \rceil\)。大胆推测 \(X\) 与 \(\operatorname{lcm}(a_1,a_2,\cdots,a_N)\) 有关。记 \(l=\operatorname{lcm}(a_1,a_2,\cdots,a_N)\)，如果存在非负整数 \(k\)，使得对于每个 \(\dfrac{l}{a_i}\)，都能表示成 \(2^k \times d\) 的形式（\(d\) 为任意正奇数），那么 \(X=\dfrac{l}{2^{k+1}}\)（把原来的 \(2\) 消去之外还要再除以 \(2\) 才能出现 \(0.5\)）。

说明一下，如果不存在这样的 \(k\)，那么用 \(X\) 除以 \(a_i\) 时会出现结果为整数的情况（即 \(X\) 分解后 \(2\) 的个数不少于 \(a_i\) 时），此时答案显然为 \(0\)。

时间复杂度 \(O(n \log A)\)，其中 \(A\) 为值域上限。

#include <iostream>
#include <cstdio>
#define int long longusing namespace std;int n,m,a[1000001],b[101],flag,lc,ans,g,cnt,ti;int gc( int x , int y )
{if( y == 0 ) return x;return gc( y , x % y );
}signed main()
{cin >> n >> m;for( int i = 1 ; i <= n ; i ++ )cin >> a[i];lc = a[1];for( int i = 2 ; i <= n ; i ++ )lc = lc * a[i] / gc( lc , a[i] );for( int i = 1 ; i <= n ; i ++ ){a[i] = lc / a[i];cnt = 0;while( a[i] % 2 == 0 ) a[i] /= 2,cnt ++;		b[cnt] ++;}ti = 1;for( int i = 0 ; i <= 34 ; i ++ ){ti *= 2;if( b[i] == n ){lc = lc / ti;ans = m / lc;ans = ans / 2 + ans % 2;cout << ans;return 0;}}cout << 0;return 0;
}

E

计数题。

首先有一个显然的贪心，即对于较大的 \(C_i\)，应分配一个较小的 \(D\)。考虑反证，设 \(C_i > C_j\) 且 \(D_1 > D_2\)，从 \(C_i \times D_2 + C_j \times D_1\) 变成 \(C_i \times D_1 + C_j \times D_2\) 的变化量为 \(C_i \times ( D_1 - D_2 ) - C_j \times ( D_1 - D_2 )=(C_i-C_j)\times (D_1-D_2) > 0\)，显然不优，因此上述贪心正确。

有了这个贪心，那么在每种状态下，每个位置被修改时的 \(D\) 也就确定了。发现状态数太多，因此换一个角度，计算每个 \(C_i\) 对于答案的贡献。影响贡献的有两个因素：\(C_i\) 被修改时的 \(D\)（可简单理解为比 \(C_i\) 大的数的个数），以及对应这个 \(D\) 的方案数。不妨先将 \(C\) 从大到小排序。

设当前在第 \(i\) 个位置，则对答案的贡献为（为了区分原题目中的 \(C_i\) 和组合数，\(C_i\) 用 \(A_i\) 表示）：

\[A_i \times 2^{n-i} \times \sum_{j=0}^{i-1} (j+1) \times C_{i-1}^{j} \]

我们分开理解这个式子的各部分：\(2^{n-i}\) 表示后面的 \(n-i\) 位修改不修改均可，不会对当前第 \(i\) 位产生影响；\(j\) 表示前面 \(i-1\) 个位置修改的个数，那么此时 \(D=j+1\)，而前面修改的方案有 \(C_{i-1}^{j}\) 种，将两者相乘即可。

直接这样做是 \(O(n^2)\) 的，还有优化的空间。回顾组合数递推的式子 \(C_i^j=C_{i-1}^j + C_{i-1}^{j-1}\)，在本题中即 \(C_{i-1}^{j}=C_{i-2}^j+C_{i-2}^{j-1}\)，还要乘上 \(j+1\) 的系数。记 \(sum_i=\sum_{j=0}^{i-1} (j+1) \times C_{i-1}^{j}\)，即

\[C_{i-1}^j \times (j+1) = C_{i-2}^{j} \times (j+1) + C_{i-2}^{j-1} \times (j+1) \]

展开最后一项并带上求和符号：

\[sum_i=\sum_{j=0}^{i-1} (j+1) \times C_{i-1}^{j}= \sum_{j=0}^{i-1} C_{i-2}^{j} \times (j+1) + C_{i-2}^{j-1} \times j + C_{i-2}^{j-1} \]

分开等式右边各部分为：

\[sum_i=\sum_{j=0}^{i-1} C_{i-2}^{j} \times (j+1) + \sum_{j=0}^{i-1} C_{i-2}^{j} \times (j+1) + \sum_{j=0}^{i-1} C_{i-2}^{j} \]

发现第一项和第二项完全等价，即为 \(sum_{i-1}\)（\(C_{i-2}^{i-1}\) 显然为 \(0\)，不会产生影响）。第三项就是杨辉三角中一行的求和，直接可得为 \(2^{i-2}\)。于是 \(sum_i=sum_{i-1}\times 2+2^{i-2}\)。初始值 \(sum_1=1\)。

实现时只需要预处理 \(2\) 的幂即可。由于只是确定了每个位修改还是不修改，并没有确定是从 \(0\) 变为 \(1\) 还是从 \(1\) 变为 \(0\)，因此最后答案要乘上 \(2^n\)。时间复杂度 \(O(n)\)。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
#define MOD 1000000007using namespace std;int n,c[1000001],p2[1000001],sum,ans,tot;bool cmp( int x , int y )
{return x > y;
}signed main()
{cin >> n;p2[0] = 1;for( int i = 1 ; i <= n ; i ++ ){cin >> c[i];p2[i] = p2[i - 1] * 2ll % MOD;}sort( c + 1 , c + n + 1 , cmp );sum = 1;for( int i = 1 ; i <= n ; i ++ ){if( i >= 2 ){tot = p2[i - 2];sum = ( sum * 2 % MOD + tot ) % MOD;}ans = ( ans + sum * c[i] % MOD * p2[n - i] % MOD ) % MOD;}cout << ans * p2[n] % MOD;return 0;
}

F

读题可以发现一个事实，即如果已求得一个合法的 \(k\)，则 \(x\) 也唯一确定了。因为 \(a_{(i+k)\bmod n} \operatorname{xor}x=b_i\)，根据异或的可逆性可得 \(x=a_{(i+k)\bmod n} \operatorname{xor} b_i\)。那么问题转化为判断每个 \(0\le k <n\) 是否合法。

不难想到暴力的做法，每次令 \(x=a_k \operatorname{xor}b_0(0\le k <n)\)，判断其它位置是否相等，时间复杂度 \(O(n^2)\)，不够优秀，瓶颈在于判断是否相等这个过程。考虑异或的本质是二进制的运算，且在某一二进制位上 \(a_i\) 要么全部不变，要么全部取反（取决于 \(x\) 二进制在该位上的数值）。又由于不同的 \(x\) 可能在某些二进制位上相同，因此每次都重新判断会出现大量冗余。

我们换个角度考虑，枚举 \(x\) 二进制下的每一位，并令该位分别等于 \(0\) 和 \(1\)，保留 \(a_i\) 当前位和 \(x\) 当前位的异或值，同时令 \(b'\) 为 \(b\) 二进制当前位的值。这样做，相当于 \(a'\) 在当前位确定下来了，直接枚举 \(k\) 判断和 \(b'\) 是否相等即可，用 Hash 即可做到 \(O(n)\)。如果某一位的 \(x\) 为 \(0\) 或 \(1\) 时均不合法，则对应 \(k\) 不合法，否则合法。

总时间复杂度 \(O(n\log A)\)，其中 \(A\) 为值域上限。

#include <iostream>
#include <cstdio>
#define int long long
#define MOD 998244853
#define base 233using namespace std;int n,A[1000001],B[1000001],a[1000001],b[1000001],c[1000001],d[1000001],sum[1000001],p[1000001],ha[1000001],hb[1000001],f[1000001],vis1[1000001],vis2[1000001];int h1( int l , int r )
{if( l > r ) return 0;return ( ( ha[r] - ha[l - 1] * p[r - l + 1] % MOD ) % MOD + MOD ) % MOD;
} int h2( int l , int r )
{if( l > r ) return 0;return ( ( hb[r] - hb[l - 1] * p[r - l + 1] % MOD ) % MOD + MOD ) % MOD;
} void js1( )
{for( int i = 1 ; i <= n ; i ++ ){ha[i] = ( ha[i - 1] * base % MOD + c[i] ) % MOD;hb[i] = ( hb[i - 1] * base % MOD + d[i] ) % MOD;}int l1,r1,l2,r2;for( int i = 0 ; i < n ; i ++ ){l2 = 1,r2 = n - i;l1 = l2 + i,r1 = n;
//		cout << i << ' ' << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;if( h1( l1 , r1 ) != h2( l2 , r2 ) ) continue;l2 = r2 + 1,r2 = n;r1 = l1 - 1,l1 = 1;
//		cout << i << ' ' << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;if( h1( l1 , r1 ) != h2( l2 , r2 ) ) continue;vis1[i] = 1;}return;
}void js2( )
{for( int i = 1 ; i <= n ; i ++ ){c[i] ^= 1;ha[i] = ( ha[i - 1] * base % MOD + c[i] ) % MOD;hb[i] = ( hb[i - 1] * base % MOD + d[i] ) % MOD;}int l1,r1,l2,r2;for( int i = 0 ; i < n ; i ++ ){l2 = 1,r2 = n - i;l1 = l2 + i,r1 = n;
//		cout << i << ' ' << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;if( h1( l1 , r1 ) != h2( l2 , r2 ) ) continue;l2 = r2 + 1,r2 = n;r1 = l1 - 1,l1 = 1;
//		cout << i << ' ' << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;if( h1( l1 , r1 ) != h2( l2 , r2 ) ) continue;vis2[i] = 1;}return;
}signed main()
{cin >> n;p[0] = 1;f[0] = 1;for( int i = 1 ; i <= n ; i ++ )p[i] = p[i - 1] * base % MOD,f[i] = 1;for( int i = 1 ; i <= n ; i ++ )cin >> a[i],A[i] = a[i];for( int i = 1 ; i <= n ; i ++ )	cin >> b[i],B[i] = b[i];for( int j = 0 ; j <= 31 ; j ++ ){vis1[0] = vis2[0];for( int i = 1 ; i <= n ; i ++ )	{c[i] = a[i] % 2;d[i] = b[i] % 2;vis1[i] = vis2[i] = 0;}js1();js2();for( int i = 0 ; i < n ; i ++ )if( !vis1[i] && !vis2[i] )f[i] = 0;for( int i = 1 ; i <= n ; i ++ )a[i] /= 2,b[i] /= 2;}for( int i = 0 ; i < n ; i ++ )if( f[i] )cout << i << ' ' << ( A[i + 1] ^ B[1] ) << '\n';return 0;
}