8月22日测试总结
8月22日测试总结
最长不互质子序列
题目大意：
给定一个长度为 \(n\) 的数组，找出最长的不互质子序列（要求：相邻的两项不互质）
思路：
1、用 \(gcd\) 判断是否能够转移
\(dp[i]=max\{dp[j]+1\}(gcd(a[i],a[j])>1,i>j)\)
2、如果 \(dp[i]\) 能从 \(dp[j]\) 转移，则 \(a[i]\) 和 \(a[j]\) 定有一个相同的质因数，这个质因数的数量是很少的。考虑重新设计状态， \(dp[i]\) 设计为最长子序列，子序列的最后一个数的质因数中含有 \(i\) 的。那么对于一个数 \(x\)，我们给它分解质因数，对于所有的质因数 \(y\)，找到最大的一个 \(dp[mxy]\)，之后把 \(dp[mxy]+1\) 更新到所有 \(dp[y]\) 中。最后枚举所有质因数即可。
3、预处理每个数字的所有质因数，每个数不同质因数的个数是 \(log\) 级别的。
这个可以在埃氏筛之类的筛法枚举质数的倍数时顺便解决。
使用邻接表之类的东西去存一下就可以了。
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+1;
int n,tot,ans;
int a[maxn];
int v[maxn*3];
int dp[maxn];
int Next[maxn*3];
int head[maxn];
int flag[maxn];
inline void inint()//埃氏筛
{
for(int i=2;i<=maxn;++i)
if(!flag[i])
for(int j=i;j<=maxn;j+=i)
{
flag[j]=1;
v[++tot]=i;
Next[tot]=head[j];
head[j]=tot;
}
}
signed main()
{
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
inint();
for(int i=1;i<=n;++i)
{
int mx=0;
for(int j=head[a[i]];j;j=Next[j])mx=max(mx,dp[v[j]]);
for(int j=head[a[i]];j;j=Next[j])dp[v[j]]=mx+1;
ans=max(ans,mx+1);
}
cout<<ans<<endl;
return 0;
}
数学课
题目大意：
给定一个长度为 \(n\) 的序列 \(A\)，在相邻两数之间可以填上 \(+,-,\times\) 三种符号，并且有 \(m\) 次操作，可以将 \(a_x\) 改为 \(y\) 。问每次修改后，所有可能的序列的答案之和，\(mod\) 1000000007 后输出
思路：
首先，因为乘法的优先性，我们可以将一串乘在一起的元素看作一个元素。
然后，由于要求的是所有可能的序列的答案之和，显然，对于一个位置，在不考虑乘法的情况下，一个位置可以是加或者减，加减抵消。那如果有乘法呢？用到上面的假设“因为乘法的优先性，我们可以将一串乘在一起的元素看作一个元素”，所以也可以抵消。
这时，我们发现，唯一一个前面没有符号，也就是不能抵消的元素是 \(a[1]\)。那么最终对答案的贡献就是每种情况下从 \(a[1]\) 开始的乘法的积（因为加减抵消），也就是前缀积。
考虑用线段树维护前缀积，每次操作影响的只会是 \(x-n\) ，这就是线段树的赋值区间。既然我们将原本的 \(a_x\) 改为了 \(y\)，那么，我们就需要除掉 \(a[x]\) 乘以 \(y\)。在模一个数的意义下，除以一个数就是乘上这个数的逆元，这就是赋的值。
Code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+1;
const int mod=1e9+7;
struct node
{
int tag,v;
}tree[maxn<<2];
int n,m;
int a[maxn];
int b[maxn];//前缀积
int d[maxn];//前缀积*出现次数（线段树维护对象）
int mul[maxn];//出现次数
inline int power(int x,int y)
{
int sum=1;
while(y)
{
if(y&1)sum=(sum*x)%mod;
x*=x;x%=mod;y>>=1;
}
return sum;
}
inline void pushup(int i){tree[i].v=(tree[i<<1].v+tree[i<<1|1].v)%mod;}
inline void pushdown(int i)
{
if(tree[i].tag==1)
return;
tree[i<<1].v=(tree[i<<1].v*tree[i].tag)%mod;
tree[i<<1|1].v=(tree[i<<1|1].v*tree[i].tag)%mod;
tree[i<<1].tag=(tree[i<<1].tag*tree[i].tag)%mod;
tree[i<<1|1].tag=(tree[i<<1|1].tag*tree[i].tag)%mod;
tree[i].tag=1;
return;
}
inline void build(int i,int l,int r)
{
if(l==r)
{
tree[i].v=d[l];
tree[i].tag=1;
return;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
pushup(i);
tree[i].tag=1;
}
inline void change(int i,int l,int r,int L,int R,int v)
{
if(R<l||r<L)
return;
if(L<=l&&r<=R)
{
(tree[i].v*=v)%=mod;
(tree[i].tag*=v)%=mod;
return;
}
pushdown(i);
int mid=(l+r)>>1;
change(i<<1,l,mid,L,R,v);
change(i<<1|1,mid+1,r,L,R,v);
pushup(i);
}
signed main()
{
std::ios::sync_with_stdio(false);
cin>>n>>m;
mul[0]=2;
b[0]=1;
for(int i=1;i<=n;++i)mul[i]=mul[i-1]*3%mod;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<n;++i)
{
b[i]=b[i-1]*a[i]%mod;
d[i]=b[i]*mul[n-i-1]%mod;
}
d[n]=b[n]=b[n-1]*a[n]%mod;//最后一个特殊处理
build(1,1,n);
while(m--)
{
int x,y;
cin>>x>>y;
change(1,1,n,x,n,y*power(a[x],mod-2)%mod);
a[x]=y;
cout<<tree[1].v<<endl;
}
return 0;
}