CodeForces1061C Multiplicity

这篇具有很好参考价值的文章主要介绍了CodeForces1061C Multiplicity。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题面翻译

从序列 \(\{a_1,\ a_2,\ ..\ ,\ a_n\}\) 中选出非空子序列 \(\{b_1,\ b_2,\ ..\ ,\ b_k\}\),一个子序列合法需要满足 \(\forall\ i \in [1,\ k],\ i\ |\ b_i\)。求有多少互不相等的合法子序列,答案对 \(10^9 + 7\) 取模。

序列 \(\{1,\ 1\}\)\(2\) 种选法得到子序列 \(\{1\}\),但 \(1\) 的来源不同,认为这两个子序列不相等。

做法

看到题目就可以联想到动态规划状态转移方程式:

\[f_{i,j}=\begin{cases}f_{i-1,j} \\f_{i-1,j}+f_{i-1,j-1}&j\mid a_i\end{cases} \]

显然,数据范围过不去。无论从空间还是时间上都超了。

优化:

空间优化:滚动数组可以把第一维优化了,因为第一维只与上一次的状态有关系。
时间优化:只有满足 \(j\)\(a_i\) 的因数时,状态才有效,所以对于每一个 \(a_i\) ,提前枚举它的因数即可,但状态不能互相影响,所以要排序。文章来源地址https://www.toymoban.com/news/detail-451869.html

代码

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cmath>
namespace FastIo{
    static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    inline void pc(const char &ch){
    	if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
    	*pw++=ch;
	}
    #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
    struct QIO{
    	char ch;
    	int st[40];
    	template<class T>inline void read(T &x){
    		x=0,ch=gc;
    		while(!isdigit(ch))ch=gc;
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
		}
		template<class T>inline void write(T a){
			do{st[++st[0]]=a%10;a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
		}
	}qrw;
}
using namespace FastIo;
#define NUMBER1 1000000
const int mod=1e9+7;
#define P(A) A=-~A
#define fione(i,a,b) for(register int i=a;i<=b;P(i))
#define fdone(i,a,b) for(register int i=a;i>=b;--i)
int a[NUMBER1+5],f[NUMBER1+5],num[NUMBER1+5],len;
signed main(){
	int n,ans(0),k;
	qrw.read(n);
	fione(i,1,n)qrw.read(a[i]);
	f[0]=1;
	fione(i,1,n){
		len=0,k=sqrt(a[i]);
		for(register int j(1);j<=k;P(j)){// 提取因数
			if(!(a[i]%j)){
				num[++len]=j;
				if(j*j!=a[i])num[++len]=a[i]/j;
			}
		}
		std::sort(num+1,num+len+1);
		fdone(j,len,1)f[num[j]]=(f[num[j]]+f[num[j]-1])%mod;//状态转移
	}
	fione(i,1,n)ans=(ans+f[i])%mod;
	qrw.write(ans);
	fsh;
    exit(0);
    return 0;
}

到了这里,关于CodeForces1061C Multiplicity的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • CodeForces CF1846G 题解

    CodeForces题目链接 洛谷题目链接 标准答案是状压之后,转化成Dijkstra算法跑最短路。我这里提供一个不一样的思路。 主人公得了病,有部分类型的症状。所有类型症状共有 (n) 种,用长为 (n) 的01串表示是否有那种症状。共有 (m) 种药,吃第 (i) 种药需要花费时间 (t_i) ,

    2024年02月14日
    浏览(38)
  • Codeforces 918(div4)

    注意一下判断 是否为平方数的方法;也要记得开long long 正序写 讨论的情况比较多,所以选择倒叙看;

    2024年02月03日
    浏览(49)
  • 快速入门 Codeforces 算法比赛/练习 网站

    Codeforces是一家为计算机编程爱好者提供在线评测系统的俄罗斯网站。同时也是广大ACM编程爱好者所喜爱,被使用的网站之一,但是有很多编程小白刚接触此类算法网站,不太熟悉如何使用,这里博主给出快速入门Codeforces的图文教程。 Codeforces官网: Codeforces 我们刚进入网站会

    2024年02月22日
    浏览(44)
  • 【Codeforces】 CF79D Password

    CF方向 Luogu方向 看到区间异或,一个经典的套路是做差分,我们即在 l l l 处异或一次,在 r + 1 r+1 r + 1 处异或一次,然后前缀和起来 于是我们可以将问题转化成:有一个序列初始全 0 0 0 ,每次可以把相隔 a i a_i a i ​ 的数都 ⊕ 1 oplus 1 ⊕ 1 ,求最少将其变成一个状态的步数

    2024年02月08日
    浏览(36)
  • codeforces A -Cut Ribbon

    基础 d p dp d p , d p i , j dp_{i,j} d p i , j ​ 表示长度为 i i i , p i e c e piece p i ece 为 j j j 的数量。题目范围 4000 4000 4000 常规定义可能会 M E L MEL ME L ,所以第二维为不同的 p i e c e piece p i ece 的个数。 枚举不同的 p i e c e s pieces p i eces 长度。 方程: d p i , j = d p i − l e n j , j +

    2024年01月18日
    浏览(33)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(54)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(43)
  • Codeforces 1855E 数学期望 + DP

    题意 传送门 Codeforces 1855E Expected Destruction 题解 将 S i S_i S i ​ 运动至 S i + 1 S_{i+1} S i + 1 ​ 的情况看作后者消失,则 S i S_i S i ​ 在碰到 S i + 1 S_{i + 1} S i + 1 ​ 前, S i + 1 S_{i + 1} S i + 1 ​ 必然存在。 根据数学期望的线性性质,可以独立地考虑每一个 S i S_i S i ​ 在碰到 S i

    2024年02月06日
    浏览(39)
  • Codeforces Round 920 (Div. 3)

    Codeforces Round 920 (Div. 3) 题意:随机给出正方形在平面坐标系上的四个顶点的坐标,求正方形的面积,正方形边与xy轴平行。 思路:因为正方形与坐标轴平行,所以找出相同的两x或y坐标即可找到一条边的长度,平方就是面积,注意结果返回整型。 AC code: 题意:给出两个01字符

    2024年01月17日
    浏览(55)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包