首页 > 其他分享 >abc132F - Small Products

abc132F - Small Products

时间:2024-01-16 09:56:47浏览次数:44  
标签:typedef const int 个块 Products abc132F Small include define

abc132F - Small Products

容易想到暴力dp,f[i][j]表示到第i个位置,且i位置上填的是j的方案数。
虽然N非常大,但是如果我们考虑按\(\frac{n}{k}\)的值分块,那么就只有根号级别的数量

\(f[i][j]\)表示在到第i个位置,且第i个位置选了第j个块中的数的方案数,那么所有能转移到第j个块的就是tot-j+1个块以及之前的,因为对于两个数x,y,如果x/k=y/k,那么能够转移到这两个数的状态集合是相同的,反过来想一个块能够转移到的状态时相同的。因此他们是两两对应的,第一个块一定对应最后一个块,第二个块一定与倒数第二个对应,以此类推。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=1e6+5;
const int S=1e5+5;
const int inf=1<<30;
const ll mo=1e9+7;
ll n,k,f[105][S],block[S],g[N],tot,l[N],t[N];
int main()
{
//	freopen("data.in","r",stdin);
	scanf("%lld %lld",&n,&k);
	for (ll i=1,j;i<=n;i=j+1) {
		j=n/(n/i);
		block[++tot]=n/i;
		l[tot]=(j-i+1);
	}
	
	fo(i,1,tot) f[1][i]=l[i];
	fo(i,2,k) {
		fo(j,1,tot) t[j]=(t[j-1]+f[i-1][j])%mo;
		fo(j,1,tot) {
			f[i][j]=(f[i][j]+ t[tot-j+1]*l[j]%mo)%mo;
		}
	}
	
	ll ans=0;
	fo(i,1,tot) ans=(ans+f[k][i])%mo;
	printf("%lld",ans);
	
	return 0;
}

	

标签:typedef,const,int,个块,Products,abc132F,Small,include,define
From: https://www.cnblogs.com/ganking/p/17966954

相关文章

  • GPT-2(small)架构推理解析
    1、有字符串BBCAD2、为字符串中的每个字母添加index索引以进行排序,A、B、C、D的索引下标分别是0、1、2、3,因此排序的数字结果为011233、将01123中的每个数字转换为c个元素的向量(这个过程称为embedding,其中c是一个超参数)4、将每个字母的索引信息分别嵌入到tokenembedding矩阵的......
  • CodeForces 1909F2 Small Permutation Problem (Hard Version)
    洛谷传送门CF传送门感觉这个题还是挺不错的。考虑F1。考察\(a_i\)差分后的意义,发现\(a_i-a_{i-1}\)就是\((\sum\limits_{j=1}^{i-1}[p_j=i])+p_i\lei\)。考虑将其转化为棋盘问题。在\((i,p_i)\)放一个车,那么\(a_i-a_{i-1}\)就是\((1,i)\sim......
  • Smalltalk 语言(面向对象的鼻祖语言)
    基础语法看一下这些基础语法,便能够读懂大部分的代码内容。注释:用双引号包围。"这是注释"字符串:用单引号包围。'这是一个字符串'单个字符:$c符号(Symbol):#thisIsASymbol大家也许对符号这个概念比较陌生。简单来说,只要两个符号的值一样,那么它们在内存中也是相同的对象。变量声明:|a|,......
  • 配置内核的时候提示Your display is too small to run Menuconfig! It must be at lea
    按照按照  (https://rocketboards.org/foswiki/Documentation/EmbeddedLinuxBeginnerSGuide)制作了一个image当想打开内核kernel的配置界面makeARCH=armmenuconfig的时候提示:scripts/kconfig/mconfKconfigYourdisplayistoosmalltorunMenuconfig!Itmustbeatleast19......
  • CF1900D Small GCD 题解
    原题链接:CF1900D,题意不多赘述。首先可以将\(a\)数组排序,并且枚举中间的那个数\(a_i\)。那么答案就是\(\sum_{j=1}^{i-1}\gcd(a_j,a_i)\times(n-i)\)。重点在于求前面的\(\gcd\)。可以用欧拉反演,但是也可以不用,因为我不会。假设我们当前已经枚举到了\(a_i\),设\(f_k\)表......
  • A Guide to Image and Video based Small Object Detection using Deep Learning : Ca
    AGuidetoImageandVideobasedSmallObjectDetectionusingDeepLearning:CaseStudyofMaritimeSurveillance基于图像和视频的小对象指南使用深度学习进行检测:的案例研究海上监视1介绍在本文中我们对2017年至2022年间发表的160多篇研究论文进行了全面回顾,以......
  • CF1900D Small GCD
    Link这是一个需要欧拉反演的题目首先,可以知道只和数字之间的大小有关,数列的顺序无关,那么就可以首先排一个序方便解决该问题。根据欧拉函数的性质,知道\(n=\sum_{d|n}\phi{(n)}\)那么我们每次先确定中间的数\(a_j\),然后根据公式,得他它得贡献是\(\sum_{i=1}^{j-1}gcd(a_{i},a_{j}......
  • ARC169 B Subsegments with Small Sums 题解
    LinkARC169BSubsegmentswithSmallSumsQuestion\(x\)是一个序列,定义\(f(x)\)为把序列\(x\)切成几段,每段的和不能超过\(S\)的最小段数给出序列\(A=(A_1,A_2,\cdots,A_N)\)求:\[\sum_{1\lel\leN}f((A_l,A_{l+1},\cdots,A_r))\]Question先考虑一个结论,\(x\)为......
  • [ABC254E] Small d and k 题解
    题目传送门一道暴力题。度数和\(k\)那么小?直接暴力\(n\)遍bfs,注意bfs的队列只能push距离不超过\(3\)的点。但有个问题,每次bfs都需要清空一次距离数组,这样子的时间复杂度是\(O(n^2)\)的。但也不难想到,距离数组中被赋值的地方不会很多,记录一下就行。Code#include......
  • Apple开发_Xcode项目中找不到Products文件、无法找到.ipa文件、无法找到打包后的静态
    1、困扰造成的困扰就是找不到.ipa文件了,如果是运行程序用来生成静态库的话,也无法找到.a后或者.framework文件了;编译出的ipa包想直接拿来用,找不到输出的ipa文件。2、解决办法2.1方法一找到项目文件.xcodeproj右击「显示包内容」打开project.pbxproj文件搜索到如下内容:mainGroup=......