ARC115简要题解
A
容易发现，两人无法有相同正确题数当且仅当两人不同答案的题数为奇数。进一步，有两人的数字和为奇数（相同答案数字和为偶数，不同答案的位置一定最终有奇数个 \(1+0=1\)。）于是答案为数字和为奇数的学生个数乘以数字和为偶数的学生个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
ll n,m,tot[2];
char s[100005][25];
int main(){
n=read(),m=read();
rep(i,1,n){
scanf("%s",s[i]+1);
int cnt=0;
rep(j,1,m)cnt+=s[i][j]-'0';
tot[cnt&1]++;
}
printf("%lld\n",tot[0]*tot[1]);
return 0;
}
### B
显然，对于存在构造的矩阵，每一行的差分数组一定相等。取元素最小的一行为 $B_i$ ，其他行与该行的差为 $A_i$ 即可。
```cpp
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int c[505][505],k=1,a[505],b[505];
inline void solve(){
int n=read();
rep(i,1,n){
rep(j,1,n)c[i][j]=read();
if(c[i][1]<c[k][1])k=i;
}
rep(i,1,n){
if(i==k)continue;
rep(j,2,n){
if(c[i][j]-c[k][j]!=c[i][1]-c[k][1]){
puts("No");return;
}
}
a[i]=c[i][1]-c[k][1];
}
puts("Yes");
rep(i,1,n)printf("%d ",a[i]);
printf("\n");
rep(i,1,n)printf("%d ",c[k][i]);
}
int main(){
solve();
return 0;
}
|
C
首先 \(p^n\) 对应的 \(A\) 值与 \(p,p^2,\dots,p^{n-1}\) 都不同，归纳得至少为 \(n\) 。同理可得对于任意 \(n\) ，\(A_n\) 最少为 \(n\) 分解质因数后的次数和，不难验证这样满足条件。线性筛即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=1e5+5;
int pri[N],d[N],t[N],tot;
bool vis[N];
inline void solve(){
int n=read();
d[1]=1;
rep(i,2,n){
if(!vis[i]){
pri[++tot]=i;
d[i]=2;
}
for(int j=1;j<=tot&&pri[j]*i<=n;j++){
vis[i*pri[j]]=1;
d[i*pri[j]]=d[i]+1;
if(i%pri[j]==0)break;
}
}
rep(i,1,n)printf("%d ",d[i]);
}
int main(){
solve();
return 0;
}
|
D
因为一张图的度数和一定是偶数，所以 \(k\) 为偶数。考虑原图是一棵树时，我们选取偶数个点的集合，选取两两之间的树上路径为边（选每条边的次数模\(2\)）。这样就证明了对于每个偶数个点的集合，都存在满足条件的子图 \(H\) 。
这样的构造唯一吗？答案是肯定的。因为 \(n\) 个点的树上有 \(2^{n-1}\) 种选取边的方式，而
（画杨辉三角或通过组合数递推式既得）
这说明我们构造的是双射，于是选 \(k\) 个点的方案数就是 \(C_n^k\) .
下面看连通图的情形，我们将边分为生成树上的边和非树边两种。对于选取的非树边集合，每条边 \((u,v)\) 都存在对应的树上路径，将所有路径选择后发现和树的情形是一样的。于是选 \(k\) 个点的方案数就是 \(2^{m-n+1}C_n^k\) .
一般图则是把所有连通分量的答案做卷积，时间复杂度为 \(O(N^2)\) 或 \(O(N\log N)\) .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61 | #include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=5e3+5,P=998244353;
int n,m,fac[N],ifac[N],tot,cur=1;
int sz[N],e[N],fa[N];
ll f[N][N],g[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int u,int v){
int fu=find(u),fv=find(v);
e[fu]++;
if(fu!=fv)fa[fv]=fu,sz[fu]+=sz[fv],e[fu]+=e[fv];
}
inline ll fpow(ll x,ll y){
ll res=1;
while(y){
if(y&1)res=res*x%P;
y>>=1;x=x*x%P;
}
return res;
}
inline ll C(int n,int m){return 1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
int main(){
n=read(),m=read();
fac[0]=1;
rep(i,1,n){
fac[i]=1ll*i*fac[i-1]%P;
fa[i]=i,sz[i]=1;
}
ifac[n]=fpow(fac[n],P-2);
rep(i,1,n)ifac[n-i]=1ll*(n-i+1)*ifac[n-i+1]%P;
rep(i,1,m){
int u=read(),v=read();
merge(u,v);
}
f[0][0]=1;
rep(i,1,n){
if(fa[i]==i){
int ni=sz[i],mi=e[i];
ll pow2=fpow(2,mi-ni+1);
for(int k=0;k<=ni;k+=2){
g[k]=pow2*C(ni,k)%P;
}
rep(j,0,ni)rep(k,0,tot){
f[cur][j+k]=(f[cur][j+k]+f[cur-1][k]*g[j]%P)%P;
}
tot+=ni,cur++;
}
}
rep(i,0,n)printf("%lld\n",f[cur-1][i]);
return 0;
}
|