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 918(div4)

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

    2024年02月03日
    浏览(51)
  • CodeForces CF1846G 题解

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

    2024年02月14日
    浏览(39)
  • 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日
    浏览(35)
  • CodeForces每日好题10.14

       给你一个字符串 让你删除一些字符让它变成一个相邻的字母不相同的字符串,问你最小的删除次数 以及你可以完成的所有方/案数 求方案数往DP 或者 组合数学推公式上面去想,发现一个有意思的事情 例如1001011110 这个字符串你划分成1  00   1 0 1111 0 每个部分最多剩余一

    2024年02月07日
    浏览(37)
  • codeforces (C++ Satisfying Constraints)

        1、找到最大的下限min 2、找到最小的上限max 3、则max-min+1满足1、2约束条件的个数 4、max-min+1减去约束条件3的个数,即为最终答案 5、如果min大于max,则结果为0,不存在满足约束条件的数

    2024年01月19日
    浏览(32)
  • 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日
    浏览(42)
  • codeforces B - Collecting Game

    比 a i a_i a i ​ 小的一定对 a n s i ans_i an s i ​ 有贡献(应该加上)。加上之后 s c o r e score score 变大,在 s c o r e score score 变大的过程中可能会有更多的 a j a_j a j ​ 小于 s c o r e score score 。 很容易想到排序,排序之后当前 s c o r e score score 就是 ∑ j = 1 i a j sumlimits_{j = 1}^ia

    2024年01月20日
    浏览(39)
  • 快速入门 Codeforces 算法比赛/练习 网站

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

    2024年02月22日
    浏览(45)
  • Codeforces Round 882 (Div. 2)

    目录 A. The Man who became a God  题目分析: B. Hamon Odyssey 题目分析: C. Vampiric Powers, anyone? 题目分析:  n个人分成k组,每一组的力量都是 这样的,那么如果分成k组那么就会有k-1个力量不被统计,将力量总和减去前k-1个最大的力量就是最小的结果   将数组分组,每个组内进行按位与

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

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

    2024年01月17日
    浏览(68)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包