首页 > 其他分享 >AHOI2022山河重整 题解

AHOI2022山河重整 题解

时间:2022-11-08 09:22:16浏览次数:48  
标签:山河 int 题解 sum -- AHOI2022 dp getchar

首先容易得到 \(O(n^2)\) 的解法,容易观察得出任意时刻范围都应是 \([1,\sum]\) 否则直接寄了。

考察 \(i\) 使得 \([1,i]\) 都能凑出但 \(i+1\) 不行。则有 \(\sum\limits_{a_x\leqslant i}a_x=i\),令 \(f_i\) 表示其方案数。

可以考虑总方案减去不可行的方案,而不可行的方案可以依据更小的 \(f\) 求出。

考察这种最多只能加 \(\sqrt n\) 的背包,其实就是对每个 \(i\in [1,\sqrt n]\) 对 \(\sum [a_x\geqslant i]\) 做完全背包。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
#define inf 1e9
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
int n,mod,dp[maxn],ans,pw[maxn],f[maxn];
inline void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}
inline void solve(int n){
	if(n<=1)return;solve(n/2);
	for(int i=0;i<=n;i++)f[i]=0;
	int lim=sqrt(2*n);
	for(int i=lim;i>=1;i--){
		for(int j=n;j>i;j--)f[j]=f[j-i];
		for(int j=i;j>=1;j--)f[j]=0;
		for(int j=0;j+(j+2)*i<=n;j++)add(f[j+(j+2)*i],dp[j]);
		for(int j=i;j<=n;j++)add(f[j],f[j-i]);
	}for(int i=n/2+1;i<=n;i++)add(dp[i],mod-f[i]);
}
int main(){
	n=read(),mod=read();
	dp[0]=pw[0]=1;
	for(int i=1;i<=n;i++)
		pw[i]=(pw[i-1]+pw[i-1])%mod;
	int lim=sqrt(2*n);
	for(int i=lim;i>=1;i--){
		for(int j=n;j>i;j--)dp[j]=dp[j-i];
		for(int j=i;j>=1;j--)dp[j]=0;
		for(int j=i;j<=n;j++)add(dp[j],dp[j-i]);
	}solve(n);
	for(int i=0;i<n;i++)
		ans=(ans+1ll*dp[i]*pw[n-i-1])%mod;
	ans=(pw[n]-ans+mod)%mod;
	printf("%d\n",ans);
	return 0;
}

深深地感到自己的弱小。

标签:山河,int,题解,sum,--,AHOI2022,dp,getchar
From: https://www.cnblogs.com/syzf2222/p/16868563.html

相关文章

  • Long数据类型序列化Json后传递给前端,产生的精度丢失的问题解决
    问题产生的原因Long类型的数据,如果我们在后端将结果序列化为json,直接传给前端的话,在Long长度大于17位时会出现精度丢失的问题。java中的long能表示的范围比js中number大,......
  • 洛谷--【P1618】三连击升级版题解 排列枚举+循环枚举+stl
    题目描述将 1,2,…,91,2,…,9 共 99 个数分成三组,分别组成三个三位数,且使这三个三位数的比例是 A:B:C,试求出所有满足条件的三个三位数,若无解,输出 No!!!。输入格式......
  • 【题解】CSP-J2022
    CSP-J2022题解/Limie T1.乘方 简要题意:给定a,b,求a^b(a^b表示a的b次方)是否大于10^9,大于输出-1,小于等于输出a^b。分析:此题直接枚举1~b会超时,故考虑用位数判断大小,a^b......
  • BUUCTF [ACTF新生赛2020]SoulLike题解(非爆破)
    查壳发现无壳。   IDA检查main函数显然先检查了输入是否以actf{开头进入sub_83A无法进入 点不进去是因为IDA限制了解析函数的长度,可以修改IDA下cfg......
  • git 问题解决
    1.fatal:theremoteendhungupunexpectedlygitconfig--globalhttp.postBuffer104857600其他方案:gitconfig--globalpack.windowMemory100mgitconfig-......
  • 【题解】codeforces 1746B Rebellion
    题意:给定一个只包含0和1的数组a,可以对a进行以下操作:选定两个下标不同的元素ai和aj,将ai加到aj上,再从数组中删除ai。问最少操作多少次,可以让数组a变成单调非下降子序列(即ai......
  • CSP-S2022题解(T4待填)
    闲话\(\huge{寄}\)\(\text{T1}\)极限脑抽,删掉暴搜打错解,\(70pts\to0pts\);\(\text{T2}\)洛谷\(100pts\)但\(\infin\)\(40pts\),很慌;\(\text{T3}\)差点想到正......
  • 2022CSP-S题解
    这次是我第一次参加\(CSP-J/S\),所以我决定口胡一下这几道题目,由于\(J\)组过于简单,就不再叙述,如有问题请私信我\(/oh/oh/oh\)假期计划(holiday)我们可以先进行\(n\)......
  • 洛谷 P3951 [NOIP2017 提高组] 小凯的疑惑 题解
    LuoguP3951[NOIP2017提高组]小凯的疑惑题解注:设\(A,B\)是两个集合,则\(A\timesB\)表示\(A\)与\(B\)的笛卡儿积(直积)。笛卡儿积的定义为\(S\timesM:=\{(s......
  • 洛谷 P2606 [ZJOI2010]排列计数 题解
    LuoguP2606[ZJOI2010]排列计数题解题目描述称一个\(1\simn\)的排列\(p_1,p_2,\dots,p_n\)是Magic的,当且仅当\[\foralli\in[2,n],p_i>p_{\lfloori/2......