A

模拟即可。

#include <bits/stdc++.h>
using namespace std;
void solve(){
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int cnt=0;string s;cin>>s;
	for(char c:s){
		cnt+=c-'0';
	}
	cout<<cnt%9<<'\n';
	return 0;
}

B

根据复数的定义直接模拟即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
struct cp{
	int x,y;
	cp(int xx=0,int yy=0){x=xx,y=yy;}
	cp operator*(cp const &b){
		return cp((x*b.x%mod-y*b.y%mod+mod)%mod,(x*b.y%mod+y*b.x%mod)%mod);
	}
};
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int n;cin>>n;cp ans(1,0);
	while(n--){
		int x,y;cin>>x>>y;
		x=(x+mod)%mod;y=(y+mod)%mod;
		cp xx(x,y);ans=ans*xx;
	}
	cout<<ans.x<<" "<<ans.y<<'\n';
	return 0;
}

C

注意到 $30=2 \times 3 \times 5$ 。令 $p_{i,j}$ 表示 $a_i$ 质因数分解后 $j$ 的指数，则答案为 $\min(\sum\limits_{i=1}^{n} p_{i,2},\sum\limits_{i=1}^{n} p_{i,3},\sum\limits_{i=1}^{n} p_{i,5})$ 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	vector<int>cnt(1000,0);
	int n;cin>>n;
	while(n--){
		int x;cin>>x;
		while(x%2==0){
			cnt[2]++;x/=2;
		}
		while(x%3==0){
			cnt[3]++;x/=3;
		}
		while(x%5==0){
			cnt[5]++;x/=5;
		}
	}
	cout<<min(min(cnt[2],cnt[3]),cnt[5])<<'\n';
	return 0;
}

D

注意到在十进制下能够影响 $\bmod 5$ 的只有数的最后一位，于是你枚举排列的最后一个数即可。答案为 $\sum\limits_{i=1}^{n}(i-1)!(i \bmod 5)$ 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int n;cin>>n;
	vector<int>fac(n+1);fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	int ans=0;
	for(int i=1;i<=n;i++){
		ans+=fac[n-1]*(i%5)%mod;
		ans%=mod;
	}
	cout<<ans<<'\n';
	return 0;
}

E

令 $f_{i,j,k}$ 表示考虑 $a$ 的前 $i$ 个数，取出其中 $j$ 个数，这些数的和为 $k$ 的方案数，显然有转移 $f_{i,j,k} \leftarrow f_{i-1,j,k}+f_{i-1,j-1,k-a_i}$ 。类似地，我们还可以求出 $g_{i,j,k}$ 表示考虑 $b$ 的前 $i$ 个数，取出其中 $j$ 个数，这些数的和为 $k$ 的方案数。则对答案数组 $ans$ 显然有转移 $ans_{x+y} \leftarrow \sum\limits_{i=0}^{n}\sum\limits_{j=0}^{i}f_{n,i,x}g_{n,j,y}$ 。滚动数组后对第二个 $\sum$ 前缀和优化即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=400;
const int mod=1e9+7;
const int M=495;
int n,a[N],b[N],f[N][M+10],g[N][M+10],ans[M+10];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];a[i]=a[i]%M;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];b[i]=b[i]%M;
	}
	f[0][0]=1;
	for(int k=1;k<=n;k++){
		int x=a[k];
		for(int i=n;i>=1;i--){
			for(int j=0;j<M;j++){
				f[i][j]+=f[i-1][(j-x+M)%M];
				f[i][j]%=mod;
			}
		}
	}
	g[0][0]=1;
	for(int k=1;k<=n;k++){
		int x=b[k];
		for(int i=n;i>=1;i--){
			for(int j=0;j<M;j++){
				g[i][j]+=g[i-1][(j-x+M)%M];
				g[i][j]%=mod;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<M;j++){
			g[i][j]+=g[i-1][j];
			g[i][j]%=mod;
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<M;j++){
			for(int k=0;k<M;k++){
				ans[(j+k)%M]+=f[i][j]*g[i][k]%mod;
				ans[(j+k)%M]%=mod;
			}
		}
	}
	for(int i=0;i<M;i++){
		cout<<ans[i]<<" ";
	}
	cout<<'\n';
	return 0;
}

F

注意到 $495=3^2 \times 5 \times 11$ 。我们令 $f_{i,j}$ 表示数 $i$ 质因数分解下 $j$ 上的指数，同时定义一个数 $x$ 所对应的三元组为 $(f_{x,3},f_{x,5},f_{x,11})$ 。显然，如果要被 $495$ 整除，这个三元组的每一位都分别不能小于 $2,1,1$ 。

首先为了方便处理，我们令每一个数所对应的三元组 $(x,y,z)$ 变为 $(\min(x,2),\min(y,1),\min(z,1))$ 。这样子的话我们一共有十二种状态。我们直接开十二颗树状数组分别维护每一个区间内对应状态的数量。然后你直接大力分类讨论两下子看看那些状态乘起来是合法的就行了。时间复杂度 $O\left(n \log n\right)$ ，但可能自带一个 $20$ 左右的常数。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int cal(int n){
	int a=0,b=0,c=0;
	while(n%3==0){
		a++;n/=3;
	}
	while(n%5==0){
		b++;n/=5;
	}
	while(n%11==0){
		c++;n/=11;
	}
	a=min(a,2ll);b=min(b,1ll);c=min(c,1ll);
	if(a==0&&b==0&&c==0) return 1;
	if(a==0&&b==0&&c==1) return 2;
	if(a==0&&b==1&&c==0) return 3;
	if(a==0&&b==1&&c==1) return 4;
	if(a==1&&b==0&&c==0) return 5;
	if(a==1&&b==0&&c==1) return 6;
	if(a==1&&b==1&&c==0) return 7;
	if(a==1&&b==1&&c==1) return 8;
	if(a==2&&b==0&&c==0) return 9;
	if(a==2&&b==0&&c==1) return 10;
	if(a==2&&b==1&&c==0) return 11;
	if(a==2&&b==1&&c==1) return 12;
    return 0;
}
struct fenwick{
	vector<int>c;int n;
	void build(int _n){
		n=_n;c.resize(n+1);
	}
	int lowbit(int x){
		return x&-x;
	}
	void add(int pos,int x){
		for(int i=pos;i<=n;i+=lowbit(i)){
			c[i]+=x;
		}
	}
	int query_pre(int pos){
		int ans=0;
		for(int i=pos;i;i-=lowbit(i)){
			ans+=c[i];
		}
		return ans;
	}
	int query(int l,int r){
		return query_pre(r)-query_pre(l-1);
	}
	int Q(int l,int r){
		return query_pre(r)-query_pre(l-1);
	}
}ds[20];
int a[N];
int d(int x){
	return x*(x-1)/2;
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int n,q;cin>>n>>q;
	for(int i=1;i<=12;i++){
		ds[i].build(n);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];a[i]=cal(a[i]);
		ds[a[i]].add(i,1);
	}
	while(q--){
		int opt;cin>>opt;
		if(opt==1){
			int x,y;cin>>x>>y;
			y=cal(y);
			ds[a[x]].add(x,-1);
			a[x]=y;
			ds[a[x]].add(x,1);
		}
		else{
			int l,r;cin>>l>>r;
			int ans=0;
			ans+=ds[7].query(l,r)*ds[6].query(l,r);
			for(int i=5;i<=7;i++){
				ans+=ds[8].query(l,r)*ds[i].query(l,r);
			}
			ans+=ds[9].query(l,r)*ds[4].query(l,r);
			ans+=ds[9].Q(l,r)*ds[8].Q(l,r);
			ans+=ds[10].Q(l,r)*ds[3].Q(l,r);
			ans+=ds[10].Q(l,r)*ds[4].Q(l,r);
			ans+=ds[10].Q(l,r)*ds[7].Q(l,r);
			ans+=ds[10].Q(l,r)*ds[8].Q(l,r);
			ans+=ds[11].Q(l,r)*ds[2].Q(l,r);
			ans+=ds[11].Q(l,r)*ds[4].Q(l,r);
			ans+=ds[11].Q(l,r)*ds[6].Q(l,r);
			ans+=ds[11].Q(l,r)*ds[8].Q(l,r);
			ans+=ds[11].Q(l,r)*ds[10].Q(l,r);
			for(int i=1;i<=11;i++){
				ans+=ds[12].Q(l,r)*ds[i].Q(l,r);
			}
			ans+=d(ds[8].Q(l,r));
			ans+=d(ds[12].Q(l,r));
			cout<<ans<<'\n';
		}
	}
	return 0;
}

周赛113题解

A

B

C

D

E

F