ARC 115

A

考虑两个人，显然选择相同不会影响，只考虑选择不同的题目个数$cnt$，注意到cnt为奇数才不可能分数相同，考虑他们选择$1$的奇偶性，相同不会影响奇偶性，不同必然会使一个人选择$1$的奇偶性发生变化，当$cnt$为奇数时，最后两个人选择1的奇偶性必然是不同的，所以把所有人按照选择$1$的奇偶性分成两个集合，然后相乘即为答案。

时间复杂度：$O(nm)$

hint

考虑对称问题：满足学生答案可能相同的对数。

$cnt$为偶数才成立，而且他们选择$1$的奇偶性最后是相同的，所以答案是：

$C_{cnt_0}^2+C_{cnt_1}^2$

code

for(int i=1;i<=n;i++){
        scanf("%s",s);int x=0;
        for(int j=0;j<m;j++)
            x+=s[j]=='1';
        a[x&1]++;
    }printf("%lld\n",1LL*a[0]*a[1]);

---

B

考虑若$a,b$答案存在，则$a$同时减小一个数$m$，$b$同时增大一个数$m$是不影响答案的，所以$a$的最小值可以为$0$，此时我们可以令$b_1$为第一列最小的数，这样就能构造出$a$的最小值为$0$，然后暴力特判即可。

时间复杂度：$O(n^2)$

code

b[0]=c[0][0];
    for(int i=1;i<n;i++) b[0]=min(c[i][0],b[0]); 
    for(int i=0;i<n;i++) a[i]=c[i][0]-b[0];
    for(int i=0;i<n;i++) b[i]=c[0][i]-a[0];
    for(int i=0;i<n;i++){
        if(b[i]<0) return puts("No"),0;
        for(int j=0;j<n;j++){
            if(a[i]+b[j]!=c[i][j]) return puts("No"),0;
        }
        }
    puts("Yes");

---

C

质因数分解，按照质因数的个数来赋值,因为倍数关系的质因数肯定不同，然后设$a_1=1$即可满足最小。

code

bitset<N>vis;
int p[N],cnt,a[N];
void ss(int n){
    vis[0]=vis[1]=1;
    a[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i]) p[++cnt]=i,a[i]=2;
        for(int j=1;j<=cnt&&i*p[j]<=n;j++){
            vis[i*p[j]]=1;
            a[i*p[j]]=a[i]+1;
            if(i%p[j]==0) break;
        }
    }
}