【HAOI2008】硬币购物
2024-09-11 08:29:30
既然没人写扩欧,那我就来一发吧。
扩欧也还好,就是跑的有点慢,然后写的时候还有点烦,不过还是卡过去了。
考场上看到这道题又蒙了。。。
怎么回事第一题又要爆零了?
然后我打了个暴力测了一下极限数据根本过不去(幸好没把电脑整死机)
于是想了又想,整出了个 $ O(s* t)$的扩欧算法(打了一个小时的样子)。
(话说正解好像容斥)
原本搞了下循环展开结果好像会更慢。。。
讲一下思路:用扩欧解。
安利扩欧博客:Judge's Class
预处理解之前我们要先用扩欧求出:
c1*x + c2*y = gcd(c1,c2) 中的 x和y (以及gcd),记录下来,
然后 c1、c2 除以 gcd(c1,c2)。(会扩欧的话就能懂吧。)
然后我们先 O(s log s) 预处理用 c1、c2 能拼出 s 的解。
(即 c1*x1 + c2*y1 = s 中 x1和y1 的解)
然后我们令 x1 达到最小正整数状态,即 y1 达到最大解。
这时如果 y1 为负数,则无解,将数组中的值设为-1,break。
否则我们用数组记录下此时的解。
那么 c3、c4 也是同理这样处理。
这样处理完之后我们发现如果没有 d 数组的限制,y/c2 就是方案数,
那么我们考虑一下 d1对x1 的限制 以及 d2 对 y1 的限制求出解的方案数。
然后记录答案在 f 数组里面,至于 c3、c4 就记录进 g 数组。
然后 O(s) 滚出答案。
//by Judge
#include<bits/stdc++.h>
#define rint register int
#define ll long long
using namespace std;
const int M=1e5+;
#idndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[<<],*p1,*p2;
inline int read(){ int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
} int c1,c2,c3,c4,d1,d2,x11,x22,y11,y22,d[];
int X1[M],X2[M],Y1[M],Y2[M],f[M],g[M];
int ex_gcd(int a,int b,int& x,int& y){ /* 套个板子,忘了就现推 */
if(!b) return x=,y=,a;
int d=ex_gcd(b,a%b,y,x);
return y-=a/b*x,d;
}
int main(){
c1=read(),c2=read();
c3=read(),c4=read();
d1=ex_gcd(c1,c2,x11,y11);
d2=ex_gcd(c3,c4,x22,y22);
c1/=d1,c2/=d1,c3/=d2,c4/=d2;
/* 预处理出解 */
for(rint s=;s<=1e5;++s){
rint tmp=s,x=x11,y=y11;
rint a=c1,b=c2;
if(tmp%d1){
X1[s]=Y1[s]=-;
continue;
}
tmp/=d1,x*=tmp,y*=tmp; y+=x/b*a,x%=b;
if(x<) x+=b,y-=a;
if(y>=) X1[s]=x,Y1[s]=y;
else X1[s]=Y1[s]=-;
}
for(rint s=;s<=1e5;++s){
rint tmp=s,x=x22,y=y22;
rint a=c3,b=c4;
if(tmp%d2){
X2[s]=Y2[s]=-;
continue;
}
tmp/=d2,x*=tmp,y*=tmp; y+=x/b*a,x%=b;
if(x<) x+=b,y-=a;
if(y>=) X2[s]=x,Y2[s]=y;
else X2[s]=Y2[s]=-;
}
for(rint T=read(),S;T;--T){
ll ans=;
for(int i=;i<=;++i)
d[i]=read();
S=read(),f[]=g[]=;
/* 考虑限制求出方案数 */
for(rint s=;s<=S;++s){
rint tmp=s,a=c1,b=c2;
rint x=X1[s],y=Y1[s];
if(x<||y<){
f[s]=;
continue;
}
rint maxX=min(x+y/a*b,d[]); if(d[]<y) x+=(y-d[]+a-)/a*b;
if(x>maxX){
f[s]=;
continue;
}
f[s]=(maxX-x)/b+;
}
for(rint s=;s<=S;++s){
rint tmp=s,a=c3,b=c4;
rint x=X2[s],y=Y2[s];
if(x<||y<){
g[s]=;
continue;
}
rint maxX=min(x+y/a*b,d[]); if(d[]<y) x+=(y-d[]+a-)/a*b;
if(x>maxX){
g[s]=;
continue;
}
g[s]=(maxX-x)/b+;
}
/* O(s) 滚出答案 */
for(rint i=;i<=S;++i)
ans+=1ll*f[i]*g[S-i];
printf("%lld\n",ans);
} return ;
}
最新文章
- OuNews 简单的新闻客户端应用源码
- Files 的值“ <; <; <; <; <; <; <; .mine”无效。路径中具有非法字符。
- mysql在linux下不区分大小写
- js的实参是按值传递还是按引用传递
- linux后台运行和关闭、查看后台任务(转)
- datalist的用法
- 由一个activity跳转到另一个activity
- wampserver2.6下UCenter1.6.0与UCenter Home2.0整合安装
- Python学习总结14:时间模块datetime &; time &; calendar (一)
- unity, SkinnedMeshRenderer.updateWhenOffscreen
- JavaScript高级---桥模式设计
- ZOJ 2624 Popo&#39;s Lamps(DP 记忆化搜索)
- lombk在IDEA中报ClassNotFoundException错误
- EF CodeFirst下数据库更新
- Spring Boot实战之数据库操作
- [Swift]LeetCode206. 反转链表 | Reverse Linked List
- 【朝花夕拾】Android Log篇
- 项目实战1—LNMP的搭建、nginx的ssl加密、身份验证的实现
- 如何让vba与java的TripleDES算法通用
- 利用奇异值分解(SVD)进行图像压缩-python实现
热门文章
- python 正则表达式re模块
- 从Paxos到Zookeeper分布式一致性原理与实践 读书笔记之(一) 分布式架构
- Kafka技术内幕 读书笔记之(六) 存储层——服务端处理读写请求、分区与副本
- Hadoop记录-Yarn命令
- 【1】【leetcode-115】 不同的子序列 distinct-subsequences
- JAVA中局部变量 和 成员变量有哪些区别
- windows修改自定义格式,有的程序写的不严谨的话会造成出错,就需要重置时间格式
- Spring AutoWire
- 【noip 2012】提高组Day2T3.疫情控制
- 集成JUnit测试错误java.lang.IllegalStateException: Failed to load ApplicationContext