首页 > 其他分享 >noip模拟7

noip模拟7

时间:2024-11-06 17:57:39浏览次数:1  
标签:const noip int long fa freopen 模拟 mod

新的阶乘

考虑从这个式子下手,怎么更优秀的求得答案。

\[\begin{aligned} f(x)&=x_1\times(x-1)^2\times(x-2)^3...2^{x-1}\times 1^x \\ &=\prod_{k=0}^{x-1}(x-k)^{k+1} \\ &=x!\times \prod_{k=0}^{x-2}(x-1-k)^{k+1} \\ &=x!\times f(x-1) \\ &=\prod_{k=1}^x k! \\ &=\prod_{k=1}^x k^{x-k+1} \end{aligned} \]

那么我们只需要考虑对于区间 \([1,n]\) 内的所有数,一个数的贡献就是质因数的个数 \(+x-k+1\)。

如果从每个数开始进行质因数分解,时间复杂度是 \(O(n\sqrt{n})\),不能接受啊。

那么我们可以仿照埃筛的思想,对于每个质数,找到它的所有倍数,对那个数进行贡献,那思路就非常清晰了。

因为会有多个同样质因数的情况,所以需要对枚举的倍数进行拆分。

总时间复杂度约为 \(O(n\log n \log \log n)\)。

能过反正。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N=1e7+7;
int ans[N];
bitset<N>vis;
void calc()
{
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])
		{
			for(int j=1;j*i<=n;j++)
			{
				vis[j*i]=1;
				int k=j*i;
				while(k%i==0) ans[i]+=(n-(j*i)+1),k/=i;
			}
		}
	}
}
void write(int x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
signed main()
{
	freopen("factorial.in","r",stdin);
	freopen("factorial.out","w",stdout);
	scanf("%lld",&n);
	calc();
	int flag=0;
	printf("f(%lld)=",n);
	for(int i=1;i<=n;i++)
	{
		if(ans[i]==0) continue;
		if(flag)putchar('*');
		if(ans[i]==1) write(i);
		else write(i),putchar('^'),write(ans[i]);
		flag=1;
	}
	return 0;
}

博弈树

结论题。

如果在直径中点那么 \(Bob\) 获胜,否则 \(Alice\) 获胜。

点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int head[N],ecnt{};
struct EDGE{
	int nxt,to;
}e[N<<2];
inline void add(int u,int v)
{
	e[++ecnt].nxt=head[u];
	head[u]=ecnt;
	e[ecnt].to=v;
}
int f[N],d[N];
int maxval{},maxpos;
inline void dfs1(int u,int fa)
{
	f[u]=fa,d[u]=d[fa] + 1;
	if(d[u]>maxval) maxval=d[u],maxpos=u;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs1(v,u);
	}
}
int dfn[N],cnt{};
inline void dfs2(int u,int fa)
{
	if(fa==0) maxval=fa;
	f[u]=fa,d[u]=d[fa]+1;
	dfn[u]=++cnt;
	if(d[u]>maxval) maxval=d[u],maxpos=u;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs2(v,u);
	}
}
vector<int>zj;
bool fnd=0;
inline void dfs3(int u,int fa)
{
	if(u==maxpos)
	{
		fnd=1;zj.push_back(u);return;
	}
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs3(v,u);
		if(fnd) {zj.push_back(u);return;}
	}
}
signed main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int n,q;cin>>n>>q;
	for(int i=1;i<n;i++)
	{
		int u,v;cin>>u>>v; 
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	int rt=maxpos;
	dfs2(rt,0),dfs3(rt,0);
	int siz=zj.size();
	int pos=0;
	if(siz%2==1) pos=zj.at(siz>>1);
	while(q--)
	{
		int u;cin>>u;
		if(pos==u) puts("Bob");
		else puts("Alice");
	}
	return 0;
}

划分

其实很简单。我们考虑分两种情况讨论。

第一种是题目给的特殊性质,满足 \(\forall i\in [1,k],a_i=0\)。这种情况就是前 \(m\) 个空,\(m\ge k\),能插最多 \(k\) 个板,那么划分成 \(k\) 段的方案数就是 \(\displaystyle\binom{m}{k-1}\)。

但是题目上说可以划分成大于等于 \(k\) 段,那总方案数就是 \(\displaystyle\sum_{i=k-1}^{m}\binom{m}{i}\)。

另一种情况,我们想到之前那个划分线段集合的题。那道题有一个贪心策略就是找 \(k-1\) 个单个的线段去确保答案最大。而这道题可以沿用这种策略。考虑选取一个长度为 \(n-k+1\) 的字典序最大的段,因为要保证最大的数的位数最多,这样才能使答案最大。其他 \(k-1\) 段就是单个的点。

然后,考虑到一个二进制数的最后一位可以更改,那么我们只需要使用哈希去匹配有多少长度为 \(n-k\) 的子串是和最大答案相匹配的,统计即为答案。

题目里有 hack 数据,你需要找一个较为优秀的模数去双哈希,要不然会有一个点卡住。

考虑有边界情况 \(n=k\),这时候答案是 \(\displaystyle \sum_{k=1}^n[a_i=1]\),方案数为 \(1\)。

顺便拿了最优解

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
const int N=2e6+5;
char c[N];
const int mod=998244353;
int mx=0;
int ppow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) res=(res*a)%mod;
		a=(a*a)%mod,b>>=1;
	}return res;
}
int f[N],g[N];
void init()
{
	f[0]=g[0]=1;
	for(int i=1;i<=n;i++)f[i]=(f[i-1]*i)%mod;
	g[n]=ppow(f[n],mod-2);
	for(int i=n-1;i>=1;i--)g[i]=(g[i+1]%mod*(i+1)%mod);
}
int getc(int a,int b)
{
	return f[a]*g[a-b]%mod*g[b]%mod;
}
#define ull unsigned long long
ull p=13331,p1=1313131;
const ull md=20091119;
ull hs[N],pp[N];
ull hs1[N],pp1[N];
signed main()
{
//	freopen("C-ex-2.in","r",stdin);
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	cin>>(c+1);
	if(n==k)
	{
		int ccnt=0;
		for(int i=1;i<=n;i++) ccnt+=(c[i]=='1');
		return cout<<ccnt<<" 1",0;
	 }

	bool _=1;
	for(int i=1;i<=k;i++) _&=(c[i]=='0');
	if(_)
	{
		int ans=0;
		for(int i=k+1;i<=n;i++) ans=((ans*2ll)%mod+c[i]-'0')%mod;
		init();
		int ans2=0,cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(c[i]=='1')break;
			++cnt;
		}
		if(cnt==n)--cnt;
		for(int i=k-1;i<=cnt;i++)ans2=(ans2+getc(cnt,i))%mod;
		cout<<ans%mod<<" "<<ans2%mod<<"\n";
		return 0;
	}
	int len=n-k+1;
	int mxpos=1;
	for(int i=1;i+len-1<=n;i++)
	{
		int j=i+len-1;
		int now=mxpos-1;
		bool flag=0;
		for(int k=i;k<=j;k++)
		{
			now++;
			if(c[k]==c[now])continue;
			if(c[k]>c[now]) {flag=1;break;}
			else break;
		}
		if(flag) mxpos=i;
	}
//	cout<<mxpos;
	int ans1=0;
	for(int i=mxpos;i<=mxpos+len-1;i++)	ans1=(ans1*2)%mod+c[i]-'0';
	for(int i=1;i<mxpos;i++) ans1=(ans1+c[i]-'0')%mod;
	for(int i=mxpos+len;i<=n;i++) ans1=(ans1+c[i]-'0')%mod;
	cout<<ans1<<" ";
	ull cmp=0,cmp1=0;pp[0]=1,pp1[0]=1;
	for(int i=1;i<=n;i++)
	{
		hs[i]=hs[i-1]*p+(int)c[i];
		pp[i]=pp[i-1]*p;
		hs1[i]=hs1[i-1]*p1%md+(int)c[i];
		hs1[i]%=md;
		pp1[i]=pp1[i-1]*p1%md;
	}
	int ans2=0;
	for(int i=mxpos;i<mxpos+len-1;i++) cmp=cmp*p+(int)c[i];
	for(int i=mxpos;i<mxpos+len-1;i++) cmp1=cmp1*p1%md+(int)c[i],cmp1%=md;
	cmp1%=md;
	for(int i=1;i+len-1<=n;i++)
	{
		ull now=hs[i+len-2]-hs[i-1]*pp[len-1];
		ull now2=((hs1[i+len-2]-hs1[i-1]*pp1[len-1]%md+md)%md+md)%md;
		if(now==cmp&&now2==cmp1)++ans2,ans2%=mod;
	}
	cout<<ans2;
	return 0;
}
/*
21 3
10010101010101110011111

10 6
0000000000

*/

灯笼

标签:const,noip,int,long,fa,freopen,模拟,mod
From: https://www.cnblogs.com/ccjjxx/p/18530685

相关文章

  • NOIP2024加赛2
    NOIP2024加赛2题目来源:2023NOIPA层联测18\(T1\)HZTG5733.新的阶乘\(100pts\)预处理素数后直接对\(1\simn\)进行质因数分解因为有太多冗余枚举导致无法通过。考虑枚举最终形式。具体地,从质因数的角度入手,设当前枚举的质数为\(p\),暴力求出\(ip\)中\(p\)的指......
  • [2024.11.06]NOIP 模拟赛
    不会tarjan不会广义串并联图……赛时T1看上去很可做。看到中位数首先想到二分。在二分的背景下,问题转化为求当前最多能使多少个元素大于等于某个定值。我们不妨先让所有的元素都选择\(a\)值,然后相当于要选择一段连续的\(b\)替换一些\(a\),要求最后总和最大。所以可以新设......
  • 11.6 模拟赛
    A.大副令\(m\)的最高一位\(1\)在\(k\)上。构造\(\lfloorn/2\rfloor\)个\(2^k\),\(n-\lfloorn/2\rfloor\)个\(2^k-1\),即可达到答案上界\((2^{k+1}-1)\times\lfloorn/2\rfloor\times(n-\lfloorn/2\rfloor)\)。B.机械师首先小甜水糖水不等式。多人同时破......
  • 7.7 g(x)=(10a)/(10b+(a-10b)e^(asinx)),取a=1.1,b=0.01,计算x=1,2,...,20时,g(x)对应的函
    importnumpyasnpimportmatplotlib.pyplotaspltfromscipy.optimizeimportcurve_fit,leastsq,least_squaresfromscipy.constantsimportedefg(x,a,b):return(10*a)/(10*b+(a-10*b)*np.exp(a*np.sin(x)))a=1.1b=0.01x_values=np.......
  • 1105模拟
    \(T1\),注意对白三角形进行搜索,每次搜到曾经走过点判断能否构成三角形是错的,我本来以为我是从总三角形中去掉每条白边影响那里错了。这启示我们什么?即使对看起来最简单的地方也要进行严谨证明,不要一眼过。然后可以想总三角形减异色三角形,就能做了\(T2\),注意如果要进行搜索,枚......
  • CSP2024 前集训:NOIP2024加赛 1
    前言赛时本来rk3,赛后自己加hack卡自己于是成rk4了。因为这场是假做法大战,T1假贪心有\(92pts\);T2\(O(n^2m)\)能过(是因为数据里\(m\le10\));T3相当抽象,赛时我打的爆搜只加了一个剪枝能得\(70pts\),赛后发现无解的时候会跑满,于是提前判掉无解就过了甚至最优解\(30ms\)......
  • 多校A层冲刺NOIP2024模拟赛18
    多校A层冲刺NOIP2024模拟赛18\(T1\)A.选彩笔(rgb)\(100pts/100pts\)观察到\(0\ler,g,b\le255\)且答案具有单调性,故考虑二分答案。将\(r,g,b\)分别抽象成三维坐标下的\(x,y,z\)。设当前二分出的答案为\(mid\),由调整法分析可知若存在一个边长为\(mid\)的......
  • NOIP模拟(flandre、meirin、sakuya、scarlet) - 模拟赛总结
    flandre做得挺久的,大约做了\(\rm1h+\)。首先,选出来的序列一定是升序的,因为交换升序序列中的任意两个都不可能让「感觉效果」更高。然后来看选那些数组成这个序列。接下来是我赛时的想法:如果全为正数,那么自然正数全部都得选。需要考虑的是负数的情况。首先,选择一个负数不仅......
  • [61] (多校联训) A层冲刺NOIP2024模拟赛18
    无论从什么意义上都能称得上挂75分的一场A.选彩笔好题答案显然可以二分突然发现我好像专长二分答案钦定最大差值\(dx\),将所有物品以\((r,g,b)\)看成三维空间坐标内的点,原问题可以转化成问空间里一个边长为\(dx\)的立方体内是否有至少\(k\)个点考虑到值域不大,可......
  • 【某NOIP模拟赛T2 - 旅游】--线段树优化 DP 的魅力
    题意:数轴上在起点\(s\)和终点\(t\)间的整点中有\(n\)个关键点,第\(i\)个关键点位置为\(c_i\),可获得\(m_i\)的价值。你可以从起点开始,每次跳至多\(z\)个点(跨过中间的点),而每到达一个\(s\)以外的点需要支付\(a\)的代价,求走到终点的最大价值。\(0\les\lec_i\let......