非常规题做题记录

· · 个人记录

A.Ancestor Relation

题面

拿到题目想到第一件事一定是先判无解。

容易发现，合法的 a_{i,j}=1 的意思是 i,j 之间有祖先关系。换种方式说，当且仅当 i,j 在不同子树中才满足 a_{i,j}=0

那么无解的第一个条件就很明显，1 是树的根所以 1 和所有点都有关系，因此 a_{1,i}=0 就是无解。

假设 u,v 两点，u 是 v 父亲，那么 u 的祖先一定全是 v 的祖先，但是 v 的祖先不一定是 u 的祖先。换成本题的 a 数组就是 a_u|a_v=a_v 那么 u 就是 v 的祖先，即 a_{u,v}=1 (a_u|a_v=a_u同理)

因此我们便找到第二个判无解条件，满足上面两条件但 a_{u,v}=0 就是一个无解。反过来如果两个条件都不满足但是 a_{u,v}=1 也是无解。

接下来考虑计算答案，但是两个不怎么相同的 a_i a_j 似乎很难直接计算贡献，那么直接考虑特殊情况。

当 a_i=a_j 时，根据上面再稍微思考一下可以想到 i,j 一定是在一条链上的，链中点的顺序是无所谓的所以每找到一条链上的点他们的贡献是点个数的阶乘。

剩下的因为没有在链上的性质无法交换位置，因此位置被固定无法贡献答案。

可以用bitset优化到 O(\frac{n^3}{w}) 但我没用。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=405;
const int mod=998244353;
int n,t;
int a[N][N];
int tag[N],lc[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    lc[0]=1;
    for(int i=1;i<=400;i++) lc[i]=lc[i-1]*i,lc[i]%=mod;
    while(t--){
        memset(tag,0,sizeof(tag));
        int ans=1;
        cin>>n;
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
        bool flag=0;
        for(int i=1;i<=n;i++) if(!a[1][i]){
            cout<<0<<"\n";
            flag=1;
            break;
        }
        if(flag) continue;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                bool f1=1,f2=1,f3=1;
                for(int w=1;w<=n;w++){
                    if(a[i][w]!=a[j][w]) f3=0;
                    if(a[i][w]&&!a[j][w]) f1=0;
                    if(!a[i][w]&&a[j][w]) f2=0;
                }
                if(f3) continue;
                if((f1&&!f2)||(!f1&&f2)){if(!a[i][j]) flag=1;}
                if((f1&&f2)||(!f1&&!f2)){if(a[i][j]) flag=1;}
                if(flag==1) break;
            }
            if(flag==1) break;
        }
        if(flag){
            cout<<0<<"\n";
            continue;
        }
        for(int i=1;i<=n;i++){
            if(tag[i]) continue;
            int p=0;
            if(i>1) p++;
            for(int j=i+1;j<=n;j++){
                bool f=1;
                for(int k=1;k<=n;k++) if(a[i][k]!=a[j][k]) f=0;
                if(f) tag[j]=1,p++;
            }
            if(p) ans*=lc[p],ans%=mod;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

B.Tree Restoring

题面

容易联想到直径。直径两端的点相隔的距离一定是最远的，并且存在的点一定是两个及以上，因此想到第一种判无解。

根据树的性质及观察样例可知，最远距离在树上一定是连续的，不可能出现父亲最远距离是 d 儿子是 d+2 ，因此得到第二种判无解。

  1. 如果最远距离是偶数，那么直径所在链形成的数一定是：

    a,a-1,a-2~~~...~~~a-k~~~...~~~a-1,a

    根据直径性质可得且 a-k 只有一个

  2. 如果最远距离是奇数，则是：

    a,a-1,a-2~~~...~~~a-k,a-k~~~...~~~a-1,a

    同理，且 a-k 有且仅有两个

剩余的点我们可以挂在直径上，它的最远距离就是它挂着点的最远距离加1，这也是为什么奇数时 a-k 有且仅有 2 个

用桶判个数即可，这就是第三种判无解(其实可以涵盖第二种)

C.Vasya And The Matrix

题面

一种很巧妙的做法。

无解很简单，整个矩形异或两遍一定是 0 ，不为 0 无解。

构造题就要构造的越简单越好，最好是每行只有一个数。假设我们把所有的数全部填在同一列就很好满足行的异或和，满足列的异或和就是放在同一行。

那么我们不妨让它们都放在最后一行和最后一列(其它也可以，只需保证行列互不干涉)。最后一个位置暂时不填，它需要满足两个约束,设答案矩形为c

c_{n,1}$$ ^ $$c_{n,2}$$ ^ $$...$$ ^ $$c_{n,m}=a_n c_{1,m}$$ ^ $$c_{2,m}$$ ^ $$...$$ ^ $$c_{n,m}=b_m

因为一个合法矩形异或两遍一定是 0 所以

a_1$$ ^ $$a_2$$ ^ $$...$$ ^ $$a_n$$^$$b_1$$ ^ $$b_2$$ ^ $$...$$ ^ $$b_m=0

根据我们的填法

c_{n,1}=b_1~...~c_{n,m-1}=b_{m-1} c_{1,m}=a_1~...~c_{n-1,m}=a_{n-1}

代回移项，观察两式

b_1$$ ^ $$b_2$$ ^ $$...$$ ^ $$a_n=c_{n,m} a_1$$ ^ $$a_2$$ ^ $$...$$ ^ $$b_m=c_{n,m}

左式相异或值为 0 因此 c_{n,m} 值是唯一的