1 题意
在第 $i$ 天,如果 $\gcd(a,b) = m – i + 1$,那么 $a,b$ 之间会建立一条边
给定 $a,b$,求 $a,b$ 最早什么时候连通
多组询问,离线
$1 \leq n ,q \leq 10^5, 1 \leq m \leq n, 1 \leq a, b \leq n$
$n,m,q,a,b \in \mathbb{Z}$
「Jump up HIGH!!」
在第 $i$ 天,如果 $\gcd(a,b) = m – i + 1$,那么 $a,b$ 之间会建立一条边
给定 $a,b$,求 $a,b$ 最早什么时候连通
多组询问,离线
$1 \leq n ,q \leq 10^5, 1 \leq m \leq n, 1 \leq a, b \leq n$
$n,m,q,a,b \in \mathbb{Z}$
考场上的时候总觉得题目非常的奇妙
因为一直循环下去不就完了吗?
直到后来我的同桌给我指点,原来把 DP 式子当方程解可以了
还是太菜啊
Continue reading “中山纪念中学 Day 4 2019.08.04 解题报告 & 题解”这个题目很像 Luogu P2290
但是问题在于,这个里面具有不确定的度数
经过简单的思考,我们可以得出以下式子
$$
C_{n – 2}^{cnt} \times \frac{sum!}{\prod_{i = 1}^{cnt} (d_i – 1)!} \times (n – cnt) ^{n – sum – 2}
$$
其中
从 ${1, 2, 3 \cdots, n – 1, n}$ 中选出 $m$ 个元素,可以重复,有多少个不同的组合?
答案 $C_{n + m – 1}^{m}$
证明
显然,问题可以转换为 $m$ 个球放入 $n$ 个盒子,可以放无数个或者不放
即插入 $n – 1$ 个隔板,然后求全排列 $(m + n – 1)!$
但是隔板和球的顺序是无效的所以除去 $m! \times (n-1)!$
即
$$
\frac{(m + n – 1)!}{m! \times (n – 1)!} = C_{n + m -1}^m
$$
题目链接: https://oj.woshiluo.site/problem/2055 / https://www.luogu.org/problemnew/show/P5323
我看到题目的一瞬间
我是在学 oi 还是在学物理?
然后我仔细思考了一下,这两个镜子来回反射,您这是要求极限?
然后我仔细思考了一下
设 $f_i$ 为从 $1$ 到 $i$ 的透光率,$g_i$ 为从 $i$ 到 $1$ 的反光率
Continue reading “「BJOI2019」光线”这道题形象生动的说明了从几何层面来找规律是多么的方便
~~打表找规律是多么的我方便~~
题目一看…
杨辉三角?
%2意义下的面积?
输出一下看看吧
1
1 1
1 1
1 1 1 1
1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1
1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
这是在每一位都%2
后只输出1
后得到的结果
好好看啊wq
你为什么不试试在这里面找找规律呢?
我们可以很明显的观察到,每一个三角形都是由下面一个三角形所叠加出来的
1
11
每个第$ 2^i $ 行,就是一个三角形的结尾
每个第$ 2^i $ 行,就是由三个第 $ 1 $ 到 $ 2^{i-1} $的三角形组成
看起来第$ 2^i $ 行的结果我们可以算出来:
$$ f(1)=1 $$
$$ f(i) = f(i/2)*3 $$
整理一下:
第 $ 2^i $ 行有 $ 3^{i-1} $ 个1
恩,快速幂大法解决就可以
问题在于,不是$2^i$的怎么办?
恩,先打表找规律吧>_<
1 : 1 1
2 : 1 1 3
3 : 1 1 5
4 : 1 1 1 1 9
5 : 1 1 11
6 : 1 1 1 1 15
7 : 1 1 1 1 19
8 : 1 1 1 1 1 1 1 1 27
9 : 1 1 29
10 : 1 1 1 1 33
11 : 1 1 1 1 37
12 : 1 1 1 1 1 1 1 1 45
13 : 1 1 1 1 49
14 : 1 1 1 1 1 1 1 1 57
15 : 1 1 1 1 1 1 1 1 65
16 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 81
17 : 1 1 83
18 : 1 1 1 1 87
19 : 1 1 1 1 91
20 : 1 1 1 1 1 1 1 1 99
21 : 1 1 1 1 103
22 : 1 1 1 1 1 1 1 1 111
23 : 1 1 1 1 1 1 1 1 119
24 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 135
25 : 1 1 1 1 139
26 : 1 1 1 1 1 1 1 1 147
27 : 1 1 1 1 1 1 1 1 155
28 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 171
29 : 1 1 1 1 1 1 1 1 179
30 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 195
31 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 211
32 : 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 243
随便推一个吧qwq
14?
首先先找到2的次幂–8
ans+=27
剩下的相当于是 第6层 ×2
以此类推qwq
以下是代码
#include <cstdio>
#include <cmath>
const long long mod=1000003;
long long sum,ans,n;
inline long long lowbit(long long x){return x&(-x);}
inline long long ksm(long long a,long long p){// 标准快速幂
long long res=1,base=a;
while(p){
if(p&1) res=(res*base)%mod;
base=(base*base)%mod;
p>>=1;
}
return res;
}
long long dfs(long long now){
long long tmp=lowbit(now);// lowbit 用于快速找到第一个我可以分层的地方
if(tmp==now){
ans=ksm(3,(std::log(now)/std::log(2)));// tmp==now 说明 now 是 2的次幂 ( log 快速求指数)
return 2; // 翻倍
}
else{
long long tmp1=dfs(now-tmp);// 剪掉算过的
ans=(ans+tmp1*ksm(3,(std::log(tmp)/std::log(2))))%mod;
return tmp1*2;
}
}
int main(){
scanf("%lld",&n);
dfs(n);
if(n%2==0) sum=(((1+n)%mod)*((n/2)%mod))%mod;
else sum=((((1+n)/2)%mod)*(n%mod))%mod;
// 都说这个地方要乘法逆元之类的高端操作...我就直接暴力了
printf("%lld",((sum-ans)%mod+mod)%mod);
}
]]> 比赛链接:[https://www.luogu.org/contestnew/show/8609]
题目链接:[https://www.luogu.org/problemnew/show/T36519]题目一看,仿佛回到了小学题目的噩梦,然而作为一位正经Oier,尝试法可不是我们应该做的,仔细一看,发现这个操作似乎有点面熟,我们来把问题抽象一下
有一个整数\(n\)最少有几个数,确保中间任意两个数相加后得到值的集合为[1,n]是不是有点眼熟?没错,这就在 初学DP(4) – 多重背包及其优化 – Codevs 3269 中的二进制优化法
1
10
100
看看上面这一串的数字是不是选择任意两个数加起来都可以得到(100)2以内的任何数?
由此可得,这道题目的答案就是n
的二进制位数+1
当然快速求位数也很简单–\(log_2(n)\)
程序:
#include <cstdio>
#include <cmath>
using namespace std;
int n;
int main(){
scanf("%d",&n);
printf("%d",(int)log2(n)+1);
}
惊不惊喜?意不意外?
题目链接:[https://www.luogu.org/problemnew/show/T36562]
DP
的思想,首先定义函数\(f(i,j)\)
其中\(i\)表示第\(i\)个数字,\(j\)表示以这个数字为结尾的数列余数为\(j\)有几种情况
很容易得到下面的代码:
#include <cstdio>
#include <cstring>
using namespace std;
int n,f,g,h,a[2100];
int dp[2100][2100];
int cnt;
inline int max(int a,int b) {return a>b?a:b;}
int main(){
scanf("%d%d",&n,&f);
for(int i=1;i<=n;i++) {scanf("%d",&a[i]);dp[i][a[i]%f]++;}// 自己的情况先加上
for(int i=1;i<=n;i++){
g=a[i]%f;// 当前数对于f的余数
for(int j=1;j<i;j++){// 遍历以前的情况
for(int k=0;k<f;k++){// 遍历余数的情况
h=(g+k)%f; // 当前的余数
dp[i][h]+=dp[j][k];// 累加
}
}
}
for(int i=1;i<=n;i++) cnt+=dp[i][0];// 统计余数为0的情况
printf("%d",cnt);// 输出
}
但是时间复杂度呢?\(O(n^2f)\)显然这个数据范围承受起来有点费劲,我们要想办法优化
观察代码发现,我们每次都是就之前的状况累加,也就是说我们没有必要对之前的情况进行遍历,只需要记住累加和就行了,但是余数这个东西比较麻烦的在于,你如何确保不被累加运算?
滚动数组解决一切
不过是不是忘记了什么???
取模啊!!!
所以正确的代码如下:
#include <cstdio>
#include <cstring>
using namespace std;
int n,f,g,h,l,a[2100],m=1e8;
int dp[2100],dp2[2100];
int cnt;
int main(){
scanf("%d%d",&n,&f);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
g=a[i]%f;
for(int k=0;k<f;k++){
h=(g+k)%f;
dp[h]+=dp2[k];
dp[h]%=m;
}
for(int k=0;k<f;k++) {dp2[k]+=dp[k];dp2[k]%=m;dp[k]=0;}
dp2[g]++;// 做到自己在把自己加上防止累加
}
printf("%d",dp2[0]);
}
题目链接: [https://www.luogu.org/problemnew/show/T36547]
#include <cstdio>
#include <cmath>
using namespace std;
int T,n,m;
int temp,temp2;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
temp=n/m*(m-1);// 正确的操作应该是temp=n/m*m; temp-=m;合并了一下
temp2=n%m;
if(temp2>0) temp2--;// 有可能n%m==0
if((temp2+temp)%2==0) printf("1\n");
else printf("0\n");
}
}
排列组合
定义: 从 \(n\) 个数中任意取出 \(m\) 个数,求有多少种方法,不同顺序算作另一种那么这种问题第一下就会想到乘法原理 对于第一位数, 有 \(n\) 种选法,对于第 2 位数, 有 \(n-1\) 种选法,对于第3位数, 有 \(n-3\) 种选法,对于第 \(y\) 位数, 有 \(n-(y-1)\) 种选法 根据乘法原理得$A_n^m=n*(n-1)*(n-2)*(n-3)*\cdots*(n-m)$ 即$A_n^m={{n!} \over {(n-m)!}}$
定义: 从 \(n\) 个数中任意取出 \(m\) 个数,求有多少种方法,不同顺序算同一种这个的区别在于不同的顺序在于同一组,不过这么相似,显然是通过上面的推得 也就是说我们要将 $A_n^m$ 中去重,那么我们就要考虑,从 \(m\) 个数中取出的长度为\(m\)的序列会有多少组不同的组合,由排列得 $A_m^m=m!$ $\therefore C_n^m={{n!} \over {m!(n-m)!}}$
题目链接:[https://www.luogu.org/problemnew/show/P2822]题目第一眼过去想让人暴力套公式计算,但是…\(t<10^4+1\) 这个速度就比较温暖人心了,有没有什么快速解决的办法的呢? 当然有!杨辉三角了解一下 当然我们不能每个数组数据都处理一波,\(n<2000+1\),后面前缀和保留每一行,后面遍历行数前缀相加就可以了 千万不要忘记边做边取模
#include <cstdio>
using namespace std;
long long t,k;
long long n,m;
long long c[2200][2200];
// n m
long long cnt=0;
long long sum[2200][2200];
inline long long min(long long a,long long b){return a<b?a:b;}
int main(){
scanf("%lld%lld",&t,&k);
for(int i=0;i<=2100;i++){//预处理
if(i==0){
for(int j=0;j<=i;j++){
c[0][j]=1;
if(c[0][j]%k==0) sum[0][j]=1;// 前缀和
else sum[0][j]=0;
}
}
else for(int j=0;j<=i;j++){
if(j==0||j==i) c[i][j]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j])%k; // 记得取模
if(j==0){
if(c[i][j]%k==0) sum[i][j]=1;
else sum[i][j]=0;
}
else {
if(c[i][j]%k==0) sum[i][j]=sum[i][j-1]+1;
else sum[i][j]=sum[i][j-1];
}
}
}
for(int i=1;i<=t;i++){//及其稀少的主部分
cnt=0;// 别忘记设0
scanf("%lld%lld",&n,&m);
for(long long j=0;j<=n;j++){
cnt+=sum[j][min(m,j)];
}
printf("%lld\n",cnt);
}
}
为什么用long long
呢,因为乘的时候可能会出事