首页 > 其他分享 >1.15模拟赛 T2题解

1.15模拟赛 T2题解

时间:2024-01-15 21:58:46浏览次数:23  
标签:cnt 1.15 int 题解 T2 num 乘法 id mod

简要题意

多重背包但是乘法

思路

暴力就直接跑背包
考虑乘法能否变为加法,可以找到模数的原根,将每个数映射一下,这样乘法就变成了加法,可以直接\(\text{bitset}\)优化,但是暴力这样做还是过不了

于是我们考虑二进制分组优化背包,这样复杂度貌似就对了?

code

#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int mod,n,op,x,ans,g;
int id[N],vis[N];
bitset<N> f;
int chk(int g){
	for(int i=1,num=g;i<mod;i++,num=1ll*num*g%mod){
		if(num==1&&i!=mod-1) return 0;
		if(num!=1&&i==mod-1) return 0;
	}
	return 1;
}
void gt_g(){
	for(g=1;g<mod;g++){
		if(chk(g)) break;
	}
	for(int i=0,num=1;i<mod-1;i++,num=1ll*num*g%mod) id[num]=i;
}
void upd(int x){
	f=f|(f<<x)|(f>>(mod-1-x));
}
int main(){
	freopen("dance.in","r",stdin);
	freopen("dance.out","w",stdout);
	scanf("%d%d",&mod,&n);
	gt_g();f[id[1]]=1;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&op,&x);
		if(!x) ans=1;
		if(op) vis[x]++;
		else f[id[x]]=1;
	}
	for(int i=1;i<mod;i++){
		int cnt=vis[i],num=i;
		for(int t=1;cnt>=t;t=t*2,num=1ll*num*num%mod){
			cnt-=t;upd(id[num]);
		}
		if(cnt){
			num=1;
			while(cnt) num=1ll*num*i%mod,cnt--;
			upd(id[num]);
		}
	}
	for(int i=0;i<mod-1;i++) ans+=f[i];
	printf("%d\n",ans);
	return 0;
}

标签:cnt,1.15,int,题解,T2,num,乘法,id,mod
From: https://www.cnblogs.com/hubingshan/p/17966443

相关文章

  • border设置渐变boder-radius不生效问题解决方案
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"/><metahttp-equiv="X-UA-Compatible"content="IE=edge"/><metaname="viewport"c......
  • 闲话1.15
    今天接着摆了。上午打了场模拟赛,接着掉分......
  • 【题解】gym103743 (2022 JSCPC)
    A.PENTAKILL!考虑直接模拟,规则就是一个人将其他人全部都击杀,并且中间没有重复击杀。code:#include<bits/stdc++.h>usingnamespacestd;map<string,vector<string>>st;intn;stringa,b;intmain(){cin>>n;for(inti=1;i<=n;++i){ci......
  • 1.15闲话
    推歌:蜥蜴舞曲/洛天依by伊野奏/Creuzer/Realillusions为啥感觉今天我闲话内容都这么少的样子,可能是因为HS_xh这几天去搞whk了导致闲话水平大幅下降(他去搞whk管我啥事今天上午帮助高一大佬去找羽毛球拍然后没找到,回来用手一抹我去怎么流鼻血了(流汗黄豆)菜菜菜菜菜菜菜菜菜菜......
  • 题解「JOI 2014 Final」IOI 馒头
    传送门。题意有\(n\)个物品,\(m\)个背包。第\(i\)个物品的价值是\(P_i\),第\(j\)个背包可以装\(C_i\)个物品,但会消耗\(E_i\)的价值。背包不能重复买,问最多可以获得多少价值。分析首先一个简单的贪心,我们在购买背包后塞入物品,一定时从大往小塞,也就是说,我们可以先对......
  • abc336 E - Digit Sum Divisible 题解 数位DP
    题目链接:https://atcoder.jp/contests/abc336/tasks/abc336_e题目大意:我们定义一个整数\(n\)的数位和为\(n\)的十进制表示中的各位上的数字之和。比如:整数\(2024\)的数位和为\(2+0+2+4=8\)。一个正整数\(n\)被称作一个好数如果\(n\)能被它的数位和整除......
  • CF1818B ndivisible 题解
    题意简述构造一个长度为\(n\)的排列\(A\),使得对于任意的\(l,r\)(\(1\lel<r\len\))都满足\(A_l+A_{l+1}+⋯+A_r\)不可以被\(r-l+1\)整除。输出其中一种合法排列即可。解题思路构造题。考虑对\(n\)进行分类讨论:当\(n=1\)时,由样例即可得合法排列为\(1\)......
  • 1.15学习进度
    18080端口为historyserver端口的WebUI,展示信息为已完成和未完成的应用信息,当4040端口关闭后,可以通过18080端口查看相关信息。   展示信息包含4040端口的所有信息演示如下:   首先创建historysever的读取路径文件夹:   mkdir/usr/local/spark/spark-events(路径可自定......
  • P6021 洪水 题解
    请先完成ddp模板一个ddp讲解视频Part0:题意解释感觉题面太阴间了。所以解释一下:Cxt表示把\(x\)结点的权值改为\(t\).Qx:把\(x\)子树中一些结点删去,使得\(x\)与\(x\)子树内所有叶子结点不连通。求删去的结点权值和的最小值。Part1:先不考虑修改操作发现原......
  • 南外集训 2024.1.15 T3
    纯粹技术性的题目。给定一个字符串的后缀数组以及对应的height数组的一部分(即一些height数组的位置是未知的,用\(-1\)表示),要求还原出一种可能的字符串。保证存在一种由\(26\)个小写英文字母构成的解。\(1\len\le10^6\)首先考虑没有\(-1\)的情况。注意到此时我们给......