首页 > 其他分享 >arc182c 题解

arc182c 题解

时间:2024-08-13 20:06:18浏览次数:13  
标签:val int 题解 arc182c 二进制 位为

arc182c

思路

有 \(6\) 个小于 \(14\) 的质数,设这 \(6\) 个质数的指数分别为 \(x_1,\dotsb,x_6\)。\(ans=\sum (\prod_{i=1}^d (x_i+1))\)。状压这 \(6\) 个数,维护 \(val_s=\prod_{i=1}^6 (x_i\times [s二进制第 i位为1]+[s二进制第 i位为0])\)。当加入一个数时,某些 \(x_i\) 会加 \(d\),\(s\) 二进制第 \(i\) 位为 \(1\) 的 \(val_s\) 会从 \(s\) 的子集且一些二进制第 \(i\) 位为 \(0\) 的 \(t\) 的 \(val_t\) 转移来。

矩阵快速幂维护转移。额外维护一个位置 \(p\) 表示答案之和,所有的 \(e[s][p]=1\)。

code

int n,m,l=64;
struct mat{
	int e[66][66];
	mat(){
		for(int i=0;i<=l;i++){
			for(int j=0;j<=l;j++)e[i][j]=0;
		}
	}
	mat operator*(const mat&tmp)const{
		mat res;
		for(int i=0;i<=l;i++){
			for(int j=0;j<=l;j++){
				for(int k=0;k<=l;k++)(res.e[i][j]+=e[i][k]*tmp.e[k][j])%=mod;
			}
		}
		return res;
	}
}bas,mul;
mat one(){
	mat res;
	for(int i=0;i<=l;i++)res.e[i][i]=1;
	return res;
}
mat ksm(mat a,int b){
	mat ans=one();
	while(b){
		if(b&1)ans=ans*a;
		a=a*a;
		b>>=1;
	}
	return ans;
}
int pre[6]={2,3,5,7,11,13};
void work(){
	n=read();m=read();
	mul.e[0][0]=1;
	for(int s=0;s<l;s++)bas.e[s][l]=1,bas.e[s][s]=m;
	bas.e[l][l]=1;
	for(int i=1;i<=m;i++){
		for(int s=0;s<l;s++){
			for(int t=1;t<=s;t++)if((s&t)==t){
				bool fl=1;
				for(int j=0;j<6;j++)if(i%pre[j]!=0&&(t&(1<<j)))fl=0;
				if(!fl)continue;
				int val=1,x=i;
				for(int j=0;j<6;j++)if(t&(1<<j)){
					int cnt=0;
					while(x%pre[j]==0)x/=pre[j],++cnt;
					val=val*cnt;
				}
				bas.e[s^t][s]+=val;
			}
		}
	}
	mul=mul*ksm(bas,n+1);
	printf("%lld\n",mul.e[0][l]-1);
}

标签:val,int,题解,arc182c,二进制,位为
From: https://www.cnblogs.com/yhddd/p/18357607

相关文章

  • CF1294F 题解
    Part.0闲话更好的观看体验目前题解区里大多数巨佬都是采用的树形dp和暴力等方法,看见没有我这种做法,欢迎指出做法问题或hack代码。Part.1题意给定一棵树,选\(3\)个点\(a,b,c\),求\(a\)到\(b\)的路径与\(a\)到\(c\)的路径与\(b\)到\(c\)的路径上一共有多少......
  • 新坑:信息学奥赛一本通题解(3001~3005)
    前言Hello,大家好我是文宇,开个新坑,是关于信息学奥赛一本通的坑,就是信奥赛题解.(这里指编程启蒙的题库)因为作者的洛谷还在写,只是信奥赛的题写的比较多,所以先做信奥赛的.信奥赛的网址是信息学奥赛一本通-编程启蒙(C++版)在线评测系统(挖坑:作者以后可能还会有信奥赛本体......
  • 生活在hzoi上 题解
    生活在hzoi上题解考虑有两棵树怎么做,显然是\(y^{n-k}=y^{n-\left\vertE_1\capE_2\right\vert}\)其中\(E_1\)和\(E_2\)是两棵树的边集发现上边那个\(k\)是两棵树边集交构成的图的连通块个数\(\left\vertE_1\capE_2\right\vert\)就是两棵树交的连通块数量......
  • 记一次NoClassDeffoundEror问题解决过程
    背景:在对某台计算服务器进行代码修改后,发现es查询报错,抛出异常如下: 思路: 1.jar包冲突   查询了对应jar的pom文件,发现只有一个es的版本jar包,不存在冲突,百思不得其解。2.本地环境问题   清理idea的缓存,发行问题仍然存在最后翻阅资料,打了断点追踪异常抛出的地方,......
  • ARC182 题解
    A-ChmaxRush!发现一个数能向哪边覆盖只由再他之后操作且\(v\)比他大的操作决定。所以扫一遍确定方向之后乘起来就好。B-|{floor(A_i/2^k)}|首先不难发现\(<2_{k-1}\)的元素是无用的,因为它们会由\(\ge2^{k-1}\)的元素除以2的幂得到。先想上界。对于\(0\l......
  • ARC182B |{floor(A_i/2^k)}| 题解
    ARC182B|{floor(A_i/2^k)}|题解题目大意定义一个长度为\(N\)的序列\(A\)的分数为能被表示成\(\lfloor{A_i\over2^k}\rfloor\)的数的个数,其中\(i=1,2,\dots,N\),\(k\)为任意自然数。给定\(N,K\),求长度为\(N\)且元素大小都在\(2^K-1\)内的所有序列的分数的最大值......
  • ARC182C
    题目C-SumofNumberofDivisorsofProduct定义一个合法的序列为:长度在\([1,n]\)间,且每个元素均为\([1,m]\)中整数的序列。定义一个合法序列的权值为:令\(X\)为序列中所有元素的乘积,则权值为\(X\)的约数个数。对所有\(\sum_{k=1}^nm^k\)个合法序列,求它们的......
  • 【题解】 [USACO 2007 FEB] Cow Party S
    题目描述题目大意给定一个有向图,以及一个顶点。求其他所有点到给定点,再从给定点回到各自起始点的最短路中的最大值。思路本题主要考查:对单源最短路算法的熟练运用。最短路总共分为2段:其他所有点到给定点、给定点回到各自起始点。首先求第一段:可以在原图的基础上建一个反向图......
  • 洛谷 P4305 不重复数字——题解
    洛谷P4305题解传送锚点摸鱼环节[JLOI2011]不重复数字题目描述给定\(n\)个数,要求把其中重复的去掉,只保留第一次出现的数。输入格式本题有多组数据。第一行一个整数\(T\),表示数据组数。对于每组数据:第一行一个整数\(n\)。第二行\(n\)个数,表示给定的数。输出格......
  • 【题解】 热浪
    题目描述【题目描述】德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪!!!他们的德克萨斯长角牛吃起来不错,可是他们并不是很擅长生產富含奶油的乳製品。FarmerJohn此时以先天下之忧而忧,后天下之乐而乐的精神,身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛......