今天感觉打的挺智力的。为啥全员 160。
感觉得了一种病，一种不挂火车头就会死的病。
看到题发现是 GDKOI 2023 提高组 D1。于是根据这两场上的时间非常近推断下一场是 D2。然后得到确凿消息明天确实要考 D2。看了看 D2 的题，T1 是个可做题，T2 是个神秘计数，T3 感觉还好。
矩阵
标算是随机一个向量 \(v\) 比较 \(v\times A\times B\) 和 \(v\times C\)。我场上写的哈希。
把 \(c_{i,j}\) 变成 \(c_{i,j}p^j\) 然后每行加起来作为哈希值，推下式子可以发现 \(A\times B\) 的哈希值算出来也是 \(O(n^2)\) 的。行算一次列算一次就行了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int mod=998244353;
int n,A[3010][3010],B[3010][3010],C[3010][3010],sum1[3010],sum2[3010];
#define add(x,y) (x+y>=mod?x+y-mod:x+y)
bool solve(int x=131){
static int a[3010][3010],b[3010][3010],c[3010][3010];
for(int i=1;i<=n;i++){
int pw=1;sum1[i]=sum2[i]=0;
for(int j=1;j<=n;j++){
pw=1ll*pw*x%mod;
a[i][j]=A[i][j];
b[i][j]=1ll*B[i][j]*pw%mod;
c[i][j]=1ll*C[i][j]*pw%mod;
sum1[i]=add(sum1[i],b[i][j]);
sum2[i]=add(sum2[i],c[i][j]);
}
}
for(int i=1;i<=n;i++){
int ans=0;
for(int j=1;j<=n;j++)ans=(ans+1ll*a[i][j]*sum1[j])%mod;
if(ans!=sum2[i])return false;
}
for(int j=1;j<=n;j++){
int pw=1;sum1[j]=sum2[j]=0;
for(int i=1;i<=n;i++){
pw=1ll*pw*x%mod;
a[i][j]=1ll*A[i][j]*pw%mod;
b[i][j]=B[i][j];
c[i][j]=1ll*C[i][j]*pw%mod;
sum1[j]=add(sum1[j],a[i][j]);
sum2[j]=add(sum2[j],c[i][j]);
}
}
for(int j=1;j<=n;j++){
int ans=0;
for(int i=1;i<=n;i++)ans=(ans+1ll*b[i][j]*sum1[i])%mod;
if(ans!=sum2[j])return false;
}
return true;
}
int read(){
int x=0;char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
return x;
}
int main(){
int tim=read();
while(tim--){
n=read();
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)A[i][j]=read();
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)B[i][j]=read();
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)C[i][j]=read();
bool jud=true;
if(!solve())jud=false;
puts(jud?"Yes":"No");
}
return 0;
}
错排
\(60\) 分比较简单，是这样一个式子：
\[\frac{(n-m)!}{(n-2m)!}\sum_{i=0}^{n-2m}(-1)^i\binom{n-2m}i(n-m-i)!
\]
推法是前面 \(m\) 个位置钦定放上数然后后边二项式反演一下。
设后边这个是 \(f_{n-m,m}\)，题解给的做法是发现有递推 \(f_{n,m}=f_{n-1,m-1}+f_{n,m-1}\)，然后每根号个 \(n\) 预处理一发，可以多项式快速幂。但是这玩意常数巨大而且实现复杂导致没人写。
实际上可以根据这个递推式整莫队。过程有点神秘。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int mod=998244353,sq=450,mx=200000;
int n,m,Q,cnt,jc[200010],inv[200010],ans[200010];
int C(int n,int m){
if(n<m)return 0;
return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
struct Ques{
int n,m,id;
bool operator<(const Ques&s)const{
return n/sq==s.n/sq?m>s.m:n<s.n;
}
}q[200010];
int main(){
jc[0]=inv[0]=inv[1]=1;
for(int i=2;i<=mx;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=mx;i++)jc[i]=1ll*jc[i-1]*i%mod;
scanf("%d",&Q);
for(int i=1;i<=Q;i++){
scanf("%d%d",&n,&m);
if(n>=2*m){
q[++cnt]={n-2*m,m+1,i};
ans[i]=1ll*jc[n-m]*jc[m]%mod;
}
}
sort(q+1,q+cnt+1);
int x,y=0,f0,f1,f2;
for(int i=1;i<=Q;i++){
if(y<q[i].m)x=0,y=mx,f0=f1=0,f2=1;
while(x<q[i].n){
x++;
f0=f1;f1=f2;
f2=1ll*(1ll*(x-1+y-1+mod)%mod*f1%mod+f0)%mod*inv[x]%mod;
}
while(x>q[i].n){
x--;
f2=f1;f1=f0;
f0=1ll*(1ll*x*f2%mod-1ll*(x-1+y-1+mod)%mod*f1%mod+mod)%mod;
}
while(y>q[i].m){
y--;
f2=(f2-f1+mod)%mod;
f1=(f1-f0+mod)%mod;
f0=(1ll*x*f2%mod-1ll*(x-1+y-1+mod)%mod*f1%mod+mod)%mod;
}
ans[q[i].id]=1ll*ans[q[i].id]*f2%mod;
}
for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
return 0;
}
异或图
好神秘。明天还有两个比这个更神秘的题。不过明天 T1 应该还是能写的。
首先考虑 \(m=0\)。就是高到低枚举位和多少个 \(1\)，看有没有 \(b\) 没顶着上界。
加上边，考虑一个暴力容斥。枚举边集，钦定它们不满足，即连通块内所有点相等。连通块大小偶数的时候没贡献，只需要对奇数的做一次上边的 dp。
爆跑是不行的，考虑枚举最后形成的连通块的集合。一个连通块的容斥系数是选边集 \(E\) 使得联通的 \(\sum(-1)^{|E|}\)。求这个可以用所有的减掉不联通的。不联通的可以枚举包含某个点的连通块，即枚举一个子集，减掉它的贡献。这个复杂度因为要枚举子集是 \(O(3^n)\)。
设 \(dp_{s,t}\) 为连通块的集合为 \(s\)，\(a\) 的集合是 \(t\) 的容斥系数之和，那么只要求出 \(dp_{2^n-1}\) 的所有值然后跑上边的做法。转移枚举一个子集枚举一个超集转移，复杂度 \(O(4^n)\)，然而好像跑的很快。
//躯樹の墓守 隣の庭は青い（庭師 + Aoi）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <unordered_map>
#define int long long
using namespace std;
const int mod=998244353;
int n,m,k,ans,a[20],w[1<<15],p[20],pos[20],to[20];
int g[20][1<<15],f[1<<15];
unordered_map<int,int>dp[1<<15];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int lowbit(int x){return x&-x;}
bool cmp(int x,int y){return a[x]<a[y];}
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=0;i<n;i++)scanf("%lld",&a[i]),a[i]++,p[i]=i;
sort(p,p+n,cmp);
for(int i=0;i<n;i++)pos[p[i]]=i;
sort(a,a+n);
for(int i=0;i<n;i++)w[1<<i]=a[i]%mod;
for(int i=1;i<=m;i++){
int u,v;scanf("%lld%lld",&u,&v);
u=pos[u-1],v=pos[v-1];
to[u]|=1<<v,to[v]|=1<<u;
}
for(int t=0;t<n;t++){
g[t][1<<t]=1;
for(int i=0;i<(1<<t);i++){
int ret=i|(1<<t);
f[ret]=(f[ret]+g[t][ret])%mod;
int tmp=i^((1<<t)-1);
for(int s=tmp;s;s=(s-1)&tmp){
if((to[t]&s)&&lowbit(s)<lowbit(ret)){
g[t][ret|s]=(g[t][ret|s]-1ll*g[t][ret]*f[s]%mod+mod)%mod;
}
}
}
}
dp[0][0]=1;
for(int i=0;i<(1<<n);i++){
int ret=((1<<n)-1)^i,pos=lowbit(ret);ret^=pos;
for(pair<int,int>x:dp[i]){
int j=x.first;
if(!x.second)continue;
for(int t=ret;;t=(t-1)&ret){
int s=t|pos;
if(__builtin_popcountll(s)&1)dp[i|s][j|pos]=(dp[i|s][j|pos]+1ll*dp[i][j]*f[s])%mod;
else dp[i|s][j]=(dp[i|s][j]+1ll*dp[i][j]*f[s]%mod*w[pos])%mod;
if(!t)break;
}
}
}
if(!k)ans=dp[(1<<n)-1][0];
for(int i=1;i<(1<<n);i++){
int tot=0;
for(int t=60;t>=0;t--){
int s=0;
for(int j=0;j<n;j++)if((i>>j)&1)s^=a[j]>>t+1;
if(s!=(k>>t+1))break;
int f=1,g=0,h=1,c=0,U=(1ll<<t)-1;
for(int j=0;j<n;j++){
if(!((i>>j)&1))continue;
if(!((a[j]>>t)&1)){
f=1ll*(a[j]&U)%mod*f%mod;
g=1ll*(a[j]&U)%mod*g%mod;
}
else{
c^=1;
int sf=f,sg=g;
f=(1ll*(a[j]&U)%mod*sg%mod+1ll*(U+1)%mod*sf%mod)%mod;
g=(1ll*(a[j]&U)%mod*sf%mod+1ll*(U+1)%mod*sg%mod)%mod;
}
h=1ll*(a[j]&U)%mod*h%mod;
}
if(!c)f=(f-h+mod)%mod;
else g=(g-h+mod)%mod;
if(!((k>>t)&1))tot=(tot+1ll*f*qpow((U+1)%mod,mod-2))%mod;
else tot=(tot+1ll*g*qpow((U+1)%mod,mod-2))%mod;
}
ans=(ans+1ll*dp[(1<<n)-1][i]*tot)%mod;
}
printf("%lld\n",ans);
return 0;
}