Promblem A 小学组
给出一个位运算操作符$\oplus \in \{or , and , xor\}$ ，和$n$个$m$维向量$a_i$，其中$a_{i,j} \in \{0,1\}$。
并给出一个最终的目标$m$维向量$x$，求出长度为$k(1\leq k \leq n)$的不重复数组$p_i$的个数，
满足$1 \leq p_i \leq n$，使得$a_{p_1,i} \oplus a_{p_2 ,i } \oplus ...\oplus a_{p_k,i} = x_i$
对于$100\%$的数据，满足$1 \leq n,m \leq 25$
Solution ：
考虑向量的维度时$m$，且比较小，而且是$0/1$，那么直接可以利用二进制状态压缩的办法将其存储。
每一次操作对于两个向量的两个相同维度做一次二进制操作，由于二进制的结合律，就相当于直接对整数做这些操作。
利用二进制运算的交换律可知，在一个确定的$p$的取值集合中交换任意两个数的顺序，不会对答案有任何影响。
那么这里，一旦一个$p$的集合合法，那么对于所有$p$集合的排列就必然合法。
注意到，空集不是一个合法的方案。
利用这两个性质，我们直接就用$O(2^n)$枚举每一个向量取不取就好了，如果合法，就加上对应的排列数。
# pragma GCC optimize(3) # include<bits/stdc++.h> # define ll long long # define Rint register int using namespace std; const int N=26; const int mo=1e9+9; char op; int n,m,base,t[N],a[N]; ll jc[N],ans; void dfs(Rint u,Rint cnt,Rint num) { if (u == n+1) { if (cnt == 0) return; if (num==base) (ans+=1ll*jc[cnt])%=mo; return; } t[u]=0; dfs(u+1,cnt,num); t[u]=1; if (op == ‘&‘) dfs(u+1,cnt+1,(num==0)?(a[u]):(num&a[u])); else if (op == ‘|‘) dfs(u+1,cnt+1,num|a[u]); else if (op == ‘^‘) dfs(u+1,cnt+1,num^a[u]); } signed main() { freopen("xx.in","r",stdin); freopen("xx.out","w",stdout); scanf("%c%d%d",&op,&n,&m); jc[0]=1;for (Rint i=1;i<=n;i++) jc[i]=jc[i-1]*i%mo; for (Rint i=1;i<=n;i++) { int num=0; for (Rint j=1;j<=m;j++) { int u; scanf("%d",&u); num=(num<<1)+u; } a[i] = num; } for (Rint i=1;i<=m;i++) { int u; scanf("%d",&u); base=(base<<1)+u; } dfs(1,0,0); printf("%lld\n",ans); return 0; }
Problem B 普及组
构造一个合法$n\times n$的矩阵$A$，需要满足下述三个条件：
$A_{i,j} \in Z $ ; 对于任意$i$都有$\prod\limits_{j = 1}^{n} A_{i,j} = X$ ; 对于任意$j$都有$\prod\limits_{i = 1}^{n} A_{i,j} = X$
其中$X$是一个所有询问前就给出的数字，现在有$T$组数据，给出$n$,求出构造矩阵的填法方案数
所有可能的$X$已知，答案对$998244353$取模。
对于$100\%$的数据满足$X$的质因子的幂次最多是$2$ , 且$1 \leq n \leq 5\times 10^6 , 1 \leq T \leq 2 \times 10^5$
Solution :
本题有一个$O(T log_2 n)$的奇怪做法。
此时相当于将前$n-1$行和$n-1$列都填$-1$或者$1$那么剩余的格子就确定了。答案就是$2^{(n-1)^2}$
首先将每行每列的乘积都变成$1$，那么就是$2^{(n-1)^2}$种情况，考虑将每行每列的焦点填上一个质数$X$，
问题就转化为将行和列匹配的方案数，那么考虑一个排列，其下标和值就是一个不同匹配，可以证明，不同的排列，其匹配是不同的。
所以此时答案就是$n! \times 2^{(n-1)^2} $
首先$1$和$-1$的填法并没有什么区别，对于每一个质因子，只是填的位置有区别。
根据乘法原理，此时答案就是$(n!)^k \times \times 2^{(n-1)^2} $， 其中$k$是不同质因子的个数。
问题就转化填数方式，使得每一行和每一列都恰好填$2$个数。
这个数列事实上可以通过打表发现规律，$f_i = \left\{\begin{matrix} 1 & i = 0,1\\ f_i = i^2 f_{i-1} - \frac{1}{2} i (i-1)^2 f_{i-2} & i \geq 2 \end{matrix}\right.$
设给出的$X$中有$a$个质因数指数幂次为$1$，$b$个质因数指数幂次为$2$,
那么这个询问的答案就是$(n!)^a \times (f_n)^b \times 2^{(n-1)^2} $
所以，对于一个询问的时间复杂度就是一个快速幂的复杂度，总时间复杂度为$O(T log_2 n)$
# pragma GCC optimize(3) # include <bits/stdc++.h> # define int long long # define putchar_ putchar using namespace std; const int mo=998244353; const int Inv2 = 499122177; const int N=5e6+10; int f[N],jc[N]; int val[N]; vector<int>H; inline int read() { int X=0,w=0; char c=0; while(c<‘0‘||c>‘9‘) {w|=c==‘-‘;c=getchar();} while(c>=‘0‘&&c<=‘9‘) X=(X<<3)+(X<<1)+(c^48),c=getchar(); return w?-X:X; } void write(int x) { if (x>9) write(x/10); putchar(x%10+‘0‘); } int Pow(int x,int n) { int ans = 1; while (n) { if (n&1) ans = ans * x % mo; x = x * x % mo; n >>= 1; } return ans % mo; } int T,x; void work1() { while (T--) { int n=read(); int ans = Pow(2,(n-1)*(n-1)); write(ans); putchar_(‘\n‘); } exit(0); } signed main() { f[0]=f[1]=jc[0]=jc[1]=1; for (int i=2;i<=5000000;i++) f[i]=((i*i%mo*f[i-1]%mo-Inv2*i%mo*(i-1)%mo*(i-1)%mo*f[i-2]%mo)%mo+mo)%mo, jc[i] = jc[i-1] * i % mo; x=read(); T=read(); if (x == 1) work1(); int a = 0 , b = 0; if(x==1)a=0,b=0; if(x==4)a=0,b=1; if(x==3)a=1,b=0; if(x==12)a=1,b=1; if(x==710701671428663075)a=2,b=3; if(x==714115052266263644)a=2,b=3; if(x==979573735390975739)a=2,b=3; if(x==640807389338647549)a=2,b=3; if(x==595630806517176908)a=2,b=3; if(x==812626144076193076)a=2,b=4; if(x==203522456999371050)a=2,b=4; if(x==421206431991626060)a=2,b=4; if(x==30)a=3,b=0; if(x==608358758975305374)a=3,b=3; if(x==598480316906172486)a=3,b=3; if(x==573010858348910652)a=3,b=3; if(x==1147387575560213988)a=3,b=7; if(x==834586893457709917)a=4,b=0; if(x==147203573614806055)a=5,b=0; if(x==371216956151518818)a=6,b=0; while (T--) { int n = read(); int ans1=jc[n]%mo; int ans2=f[n]%mo; int ans = Pow(ans1,a) * Pow(ans2,b) % mo * Pow(2,(n-1)*(n-1)) % mo; write(ans); putchar_(‘\n‘); } return 0; }
Problem C 提高组
有$T$组询问，给出$x,y$,求出最长下降子序列长度不超过$2$的排列$p$且$p_x = y$。
输出排列数对$10^9 + 7$取模的答案。
对于$100\%$的数据满足$1 \leq T \leq 10^6 , 1 \leq n \leq 10^7$
Solution :
原文：https://www.cnblogs.com/ljc20020730/p/11761057.html
