noone___'s blog
0%

50801202-AGC003

发表于 更新于 分类于
AGC003

D

给定 $n$ 个数 ，要求从中选出最多的数，满足任意两个数之积都不是完全立方数

考虑对数 $x$ 进行唯一分解，即将其每个质因子的指数对 $3$ 取模得到数 $a$ , 在对 $a$ 的每个质因子的指数的相反数对 $3$ 取模得到 $a$ 的补数 $b$ ,满足 $a\times b$ 是完全立方数

对于数列中的分解数集与其补数集，贪心选取较大的内个，注意特判最简数与其补数相等时（即 $x$ 是完全平方数）只能选一个

重点求如何分解数与分解数的补数

筛出 $10^{\frac{10}{3}}$ 内的质数，求出该范围内的分解数与补数，对于剩余的数分解质因数最多 $2$ 项，特判是否为完全平方数

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
const int p[]={2,3,5,7,11,13,17,19,23,29,31,37},S=127;
const int N=1e5+5;
vector<ll> pd;
int n,c[N],ans;
ll a[N],b[N];
map<ll,int> h,vis;

inline ll qpow(ll a,ll b,ll n){ ll ret=1; for(;b;b>>=1,a=a*a%n) if(b&1) ret=a*ret%n; return ret;}
ll gcd(ll a,ll b){ return b ? gcd(b,a%b) : a;}
inline bool miller_rabin(ll n){
    if(n==1) return false;
    for(rei i=0;i<12;++i) if(n%p[i]==0) return n==p[i];
    ll r; rei t;
    for(r=n-1,t=0;~r&1;r>>=1,++t);
    for(rei i=0;i<12;++i){
        ll x=qpow(p[i],r,n),xs;
        for(rei j=1;j<=t;++j){
            xs=x*x%n;
            if(xs==1 && x!=1 && x!=n-1) return false;
            x=xs;
        }
        if(x!=1) return false;
    }
    return true;
}

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=2200;++i) if(miller_rabin(i)) pd.push_back(i);
    for(rei i=1;i<=n;++i){
        ll x,t; scanf("%lld",&x); a[i]=b[i]=1;
        for(rei k=0;k<pd.size();++k){
            c[k]=0;
            while(x%pd[k]==0) ++c[k],x/=pd[k];
            c[k]%=3;
            if(c[k]==2) a[i]*=pd[k]*pd[k],b[i]*=pd[k];
            else if(c[k]==1) a[i]*=pd[k],b[i]*=pd[k]*pd[k];
        }
        t=sqrt(x);
        if(t*t==x) a[i]*=t*t,b[i]*=t;
        else a[i]*=x,b[i]*=x*x;
        ++h[ a[i] ];
    }
    for(rei i=1;i<=n;++i){
        if(vis[ a[i] ]||vis[ b[i] ]||a[i]==1) continue;
        vis[ a[i] ]=1; ans+=max(h[ a[i] ],h[ b[i] ]);
    }
    printf("%d\n",ans+(h[1]!=0));
    getchar(),getchar();
    return 0;
}

E

初始为 $1$ 到 $n$ 的数列，每次操作把数组长度变为 $q_i$ ，新增的数为上一个操作后的数组的重复，求最终每个数出现的次数

这个题作为 $E$ 题好像有点水（逃

首先容易发现，对于每次操作，只有长度单调递增的操作对答案有贡献

考虑每次操作 $q$ 对数组 $A={a_1,a_2…a_n}$ 的影响：

题目要求维护 $ans[N]$，那么倒序维护系数 $k$ ，对于剩下的一部分递归继续分解

最后的答案用差分维护

经典不会表述，经典看不懂赛时代码

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
const int N=1e5+100;
ll k[N],delta[N],sta[N],top;
int n,q;

void decompose(ll lenth,ll k_add){
    rei it=upper_bound(sta+1,sta+1+top,lenth)-sta-1;//注意这里要找剩下的
    if(!it) return delta[1]+=k_add,delta[lenth+1]-=k_add,void();
    k[it]+=(ll) (lenth/sta[it])*k_add;
    decompose(lenth%sta[it],k_add);
}

int main(){
    scanf("%d%d",&n,&q),sta[++top]=(ll) n;
    for(rei i=1;i<=q;++i){
        ll x; scanf("%lld",&x);
        while(top && x<=sta[top]) --top;
        sta[++top]=x;
    }
    k[top]=1ll;
    for(rei i=top;i>=2;--i){
        k[i-1]+=(sta[i]/sta[i-1])*k[i];
        decompose(sta[i]%sta[i-1],k[i]);
    }
    delta[1]+=k[1],delta[ sta[1]+1 ]-=k[1];
    for(rei i=1;i<=n;++i) printf("%lld\n",delta[i]+=delta[i-1]);
    getchar(),getchar();
    return 0;
}

F

给定一个 $n\times m$ 的黑白网格，保证黑格四连通且至少有一个黑格，定义分形如下：$0$ 级分形是一个 $1\times 1$ 的黑色单元格。$k+1$ 级分形由 $n$ 行 $m$ 列较小一级的分形按网格的样式拼成：与黑色单元格对应的位置是一个 $k$ 级分形；与白色单元格对应的位置是一个全部为白色，尺寸与 $k$ 级分形相同的网格。求 $k$ 级分形的四联通数量

看个图直观一点

https://pic.imgdb.cn/item/616d1ebe2ab3f51d91a7c34c.png

考虑无向图 $G$ ，其中的点与 $1$ 级分形一一对应，将对应至少一个位置的黑发四联通的点连边

求$k$ 级分形对应的 $G$ 的连通分量数

显然 $G$ 的连边情况与网格的上下，左右的黑格位置是否重复有关，设 $lr,ud$ 分别表示上下，左右的黑格位置重复的个数，$v$ 表示原网格中黑格的个数，$ev,eh$ ：垂直/水平方向的相邻黑格的个数

  • 若 $lr>0 \wedge ud>0$，归纳可得 $G$ 任意两点均连通，故答案为 $1$。

  • 若 $lr=0 \wedge ud=0$，归纳可得 $G$ 任意两点均不连通，故答案为 $v^{k-1}$。

  • 若 $lr>0 \wedge ud=0$，将网格逆时针旋转 $\frac{1}{4}$ 周变为情况 $4$。

  • 若 $lr=0 \wedge ud>0$，我们可以发现所有边都是垂直方向的，故 $G$ 一定是若干条垂直方向的链组成的。

链是树，我们可以用 $C=V-E$ 来计算连通分量数。

有性质: $k$ 级分形等于把 $k-1$ 级分形的每个黑格替换成一个 $1$ 级分形。可以归纳证明。

那么考虑计算 $k$ 级分形对应的图 $G_k$ 中的点数 $V_k$ 和边数 $E_k$ ，有递推式：

$V_k=V_{k-1}\times v ,V_1=1$

$E_k=E_{k-1}\times ud + V_{k-1}\times ev ,E_1=0$

所以矩阵乘法计算 $V,E$ 线性递推

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
const int N=1e3+100;
const int mod=1e9+7;
ll k;
char s[N][N];
int n,m,p,q,a,b,c;
struct Matrix{
    int Mat[2][2];
    Matrix(){ memset(Mat,0,sizeof(Mat));}
    int* operator [](const int i){ return Mat[i];}
    Matrix operator*(Matrix &mat)const{
        Matrix ret;
        for(rei i=0;i<2;++i) for(rei j=0;j<2;++j) for(rei k=0;k<2;++k)
            ret[i][j]=(ret[i][j]+(ll) Mat[i][k]*mat[k][j]%mod)%mod;
        return ret;
    }
    void set(){ for(rei i=0;i<2;++i) Mat[i][i]=1;}
}f;
Matrix qpow(Matrix a,ll b){ Matrix ret;ret.set(); for(;b;b>>=1,a=a*a) if(b&1) ret=ret*a; return ret;}

int main(){
    scanf("%d%d%lld",&n,&m,&k);
    for(rei i=1;i<=n;++i) scanf("%s",s[i]+1);
    for(rei i=1;i<=n;++i) p+=s[i][1]=='#'&&s[i][m]=='#';
    for(rei i=1;i<=m;++i) q+=s[1][i]=='#'&&s[n][i]=='#';
    if((p&&q) || k<2) return puts("1"),0;
    b=p|q;
    for(rei i=1;i<=n;++i) for(rei j=1;j<=m;++j){
            c+=s[i][j]=='#';
            a+=s[i][j]=='#' && s[i][j+1]=='#' && p;
            a+=s[i][j]=='#' && s[i+1][j]=='#' && q;
        }
    f[0][0]=c,f[1][0]=a,f[1][1]=b;
    f=qpow(f,k-1);
    printf("%d\n",(f[0][0]-f[1][0]+mod)%mod);
    getchar(),getchar();
    return 0;
}