书海扬帆的博客

题目

n对夫妇过情人节,每一位男士送每一位女士若干朵玫瑰,若一位男士送给别人妻子的花的数量总和≥送给自己妻子的花的数量,那么妻子就会不高兴。当他们互相赠送完毕后发现,对于任意一位妻子,她均可以把所有的男士分为两组,使得每组男士送给自己的花的数目之和一样多。

求证:至少有一位妻子会不高兴。

来源

白俄罗斯竞赛题。

思路

反证法。本题虽然披着组合数学难题的外衣,但本质上是一道代数题。运用数学语言和符号将所有已知条件都表示出来,就能看出端倪。

解答

将所有男士编号为${a_1},{a_2},{a_3},…,{a_n} $, 所有女士编号为${b_1},{b_2},{b_3},…,{b_n}$.用${A[i][j]} $表示第i位丈夫送给第j位妻子的花的数量。

则本题就是考察一个$n*n$的二维数组。

反证法,假设没有妻子不高兴,则对于所有的$ j \in \{1,2,…,n\} $, 均有$ A[j][j]>\sum\limits_{i = 1}^n {A[j][i]}-A[j][j]$.

移项,化简得$A[j][j] > \sum\limits_{i = 1}^n {A[j][i]}$.

对于所有的$j \in \{1,2,…,n\}$,均有.

.

矛盾!证毕!

来自某位巨佬在WC上学的技巧。

题目


给定正整数$n(n<=15000)$,计算$2^n-1$的值。

解题思路


这道题目是非常典型的高精度,但是数据范围乍一看有些吓人。普通的高精如果不慎,甚至会超时。

适用范围


仅适用于计算$2^n$的精确值,且 $|n|<=2^{14}$

浮点数能精确表示$2^n$,因为大部分浮点数内部都以2为底数,n的范围与浮点数类型有关。常用浮点数最高精度的long double也只有15位阶码。

使用方法


直接使用pow函数即可计算。

C++


字符串流输出

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
cout.precision(n>0?0:-n);
cout<<fixed<<pow(2.0L,n)<<endl;
return 0;
}

printf输出

1
2
3
4
5
6
7
8
9
#include<stdio.h>
#include<math.h>
int main(void)
{
int n;
scanf("%d",&n);
printf("%.*Lf\n",n>0?0:-n,powl(2.0L,n));
return 0;
}

浮点数常量的L后缀表示long double

Windows下scanf/printf


Windows下通常使用MinGW,部分版本可能无法正常使用%lld%Lf

解决方法非常简单,在程序首部加入:

1
#define __USE_MINGW_ANSI_STDIO 1

题解


由于n的范围刚好可以使用上述技巧,而且-1也很方便,直接在最低位-1即可,显然不会退位。

程序清单


1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
stringstream ss;
ss.precision(0);
ss<<fixed<<pow(2.0L,n);
string s=ss.str();
s[s.length()-1]--;
cout<<s<<endl;
return 0;
}

这里利用了字符串流,当然用sprintf也完全没有问题。实测比手写高精度快很多,代码也很简单。

转载自:https://www.cnblogs.com/igaoshang/articles/Zeller.html

历史上的某一天是星期几?未来的某一天是星期几?关于这个问题,有很多计算公式,其中最著名的是蔡勒 (Zeller)公式:

以2049年10月1日(100周年国庆)为例,用蔡勒(Zeller)公式进行计算,过程如下:

$W=Y+[Y/4]+[C/4]-2C+[26×(M+1)/10]+D-1​$

$=49+[49/4]+[20/4]-2×20+[26×(10+1)/10]+1-1
=49+[12.25]+5-40+[28.6]​$

$=49+12+5-40+28​$

$=54.​$

54除以7余5, 即2049年10月1日(100周年国庆)是星期五。

提高组的数论题。

这道题目我自行思考并在十分钟内写出了正解,一种成就感油然而生。思路就是GCD/LCM再加上快速幂,反复根据同余取模。

学小学奥数的时候做这类周期问题做多了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll n,m,k,x;
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
ll lcm(ll a,ll b){
ll now=gcd(a,b);
return (a/now)*(b/now)*now;
}
ll qmi(ll a,ll n,ll p){
ll m1=a,m2=n,ans=1;
while(n){
if(n%2) ans=(ans*a)%p;
a=(a*a)%p;
n/=2;
}
return ans;
}
int main(){
cin>>n>>m>>k>>x;
k=qmi(10,k,lcm(n,m));
k=(k*m)%n;
cout<<(x+k)%n<<endl;
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e7 + 15;
int n[MAXN], m[MAXN], T, inv[MAXN], p1[MAXN], p2[MAXN], prime[MAXN], flag[MAXN], o[MAXN];
int Max, R;
inline int read() {
char ch = getchar(); int u = 0, f = 1;
while (!isdigit(ch)) {if (ch == '-')f = -1; ch = getchar(); }
while (isdigit(ch)){u = u * 10 + ch - 48; ch = getchar(); }return u * f;
}
inline int ksm(long long x, int k){
long long cnt = 1;
while (k){
if (k & 1)cnt = cnt * x % R;
x = x * x % R;k >>= 1;
}
return cnt;
}
signed main(){
T = read(); R = read(); inv[1] = 1; o[1] = 1;
for (register int i = 1; i <= T; i++) {
n[i] = read(); m[i] = read();
Max = max (Max, max (n[i], m[i]));
}
for (register int i = 2; i <= Max + 10; i++) {
if (!flag[i]) prime[++prime[0]] = i;
o[i] = 1ll * o[i - 1] * i % R;
for (register int j = 1; j <= prime[0] && prime[j] * i <= Max + 10; j++){
flag[prime[j] * i] = 1;
if (i % prime[j] == 0)break;
}
}
int cnt = 1;
p1[0] = 1; p2[0] = 1; prime[++prime[0]] = 1e9 + 10;
for (register int i = 1; i <= Max + 10; i++){
p1[i] = p1[i - 1]; p2[i] = p2[i - 1];
while (prime[cnt] <= i){
p1[i] = 1ll * p1[i] * prime[cnt] % R;
p2[i] = 1ll * p2[i] * (prime[cnt] - 1) % R; cnt++;
}
}
for (register int i = 1; i <= T; i++)
printf("%lld\n", 1ll * p2[m[i]] % R * o[n[i]] % R * ksm(p1[m[i]], R - 2) % R);
return 0;
}

题目


给定整数n,求卡特兰数的第n项。

分析


利用杨辉三角性质打表算出组合数即可计算。

代码分享


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
//Catalan数:求C(2n,n)/n+1
long long a[100][100],n;

int main() {
scanf("%lld",&n);
a[1][1]=a[1][2]=1;
for(long long i=2;i<=2*n;i++){
for(long long j=1;j<=i+1;j++){
a[i][j]=a[i-1][j]+a[i-1][j-1];
//printf("%d ",a[i][j]);
}
//printf("\n");
}
long long ans=a[2*n][n+1]/(n+1);
printf("%lld\n",ans);
return 0;
}

数论是一门很棒的学科。在信息学竞赛中,数论算法一直是学习的重点、难点。它的代码实现较为简单,却不容易建立模型求解。因此,多加练习是解决这类题目的好方法。像大牛说的一样,“题做多了,考题都变成原题了”。

一句话题意

\[ 给定正整数p,求2^{2^{2^{2^...}}}(无限个2)mod\ p.\]

解法


首先来介绍一下欧拉函数及欧拉定理。

欧拉函数:设n是一个正整数,欧拉$ \varphi $函数$ \varphi(n) $定义为不超过n且与n互质(也称互素)的正整数的个数。

欧拉定理:设m是一个正整数,a是一个整数且$(a,m)=1 $(即:a, m互质),那么

接下来,我们引入扩展欧拉定理

这个定理不要求a和p互质,可以直接使用。

参考证明-来自知乎专栏

回到题目中,设$a=2,n=2^{2^{2^…}} $,由于有无穷个2,

所以有.

可以发现$ a^n \bmod p$和$a^n \bmod \varphi(p)$是一样的,所以我们可以递归求解。

边界条件:当$a^n \bmod p$为定值时结束。我们可以知道当$p=1$时这个式子必然等于0,可以结束。

这样时间复杂度是$ O(\log\ p) $的。这样加上快速幂就能求解了。

代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
#define R register
#define I inline
//宏定义
template<class T>void read(T &x) {
register int c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
//读入优化
inline ll qpow(ll x,ll y,ll p)
{
register ll ans=1;
while(y)
{
if(y&1) ans=ans*x%p;
x=x*x%p,y>>=1;
}
return ans;
}
inline ll phi(ll x)
{
register ll i,ans=x;
for(i=2;i*i<=x;i++)
{
if(x%i==0)
{
ans=ans/i*(i-1);
while(x%i==0) x/=i;
}
}
if(x!=1) ans=ans/x*(x-1);
return ans;
}
inline ll calc(ll p)
{
if(p==1) return 0;
register ll res=phi(p);
return qpow(2,calc(res)+res,p);
}
int main(){
register int t;
register ll p;
read(t);
for(register int i=1;i<=t;i++)
{
read(p);
printf("%lld\n",calc(p));
}
return 0;
}

参考资料


https://www.cnblogs.com/GXZlegend/p/6950483.html

https://blog.csdn.net/popoqqq/article/details/43951401/

https://zhuanlan.zhihu.com/p/24902174

题目传送门

Click here.

解题思路

首先可以得到至少需要n个山洞。
从小到大枚举山洞个数,可以发现,野人永远无法相遇的情况就是扩展欧几里得无解的情况。
具体的还是看代码吧。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn=20;
ll n,ans,c[maxn],p[maxn],l[maxn];
ll gcd(ll a,ll b) {
return b==0?a:gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &x,ll &y) {
if(!b) {x=1;y=0;return;}
exgcd(b,a%b,x,y);
ll z=x;x=y;y=z-a/b*y;
}
ll mx=-1;
void Get_Data() {
scanf("%lld",&n);
for(ll i=1;i<=n;i++) {
scanf("%lld%lld%lld",&c[i],&p[i],&l[i]);
mx=max(mx,c[i]);
}
}
bool check(ll x) {
for(ll i=1;i<=n;i++) {
for(ll j=i+1;j<=n;j++) {
ll A=p[j]-p[i];
ll B=x;
ll C=c[i]-c[j];
ll X=0,Y=0;
ll G=gcd(A,B);
if(C%G==0) {
A/=G;B/=G;C/=G;
exgcd(A,B,X,Y);
if(B<0) B=-B;
X=((X*C)%B+B)%B;
if(!X) X+=B;
if(X<=min(l[i],l[j])) return 0;
}
}
}
return 1;
}
void Solve() {
for(ll i=mx;;i++) {
if(check(i)) {
printf("%lld\n",ans=i);
return ;
}
}
}
int main() {
Get_Data();
Solve();
return 0;
}

题面传送门

解题思路


组合数与杨辉三角有着千丝万缕的联系,不得不说小学奥数的知识在OI中用处还是蛮大的。(不知道杨辉三角是啥?)杨辉三角与组合数最重要的一个联系在于,第n行的m个数可表示为$ \left( {\begin{array}{*{20}{c}} {m - 1}\\ {n - 1} \end{array}} \right) $,即为从n-1个不同元素中取m-1个元素的组合数。

这就意味着对于每一次询问,我们无需现算出组合数的值,采用打表来实现即可。这样一来,时间复杂度就大大降低了。

那么预处理好杨辉三角形,还有T组询问怎么办?

我们可以用一个叫做矩阵和(又叫做二维前缀和)的东西(就是下面的S数组)。

给个口诀吧:上加左 减左上 加自己

这样预处理只需要2000*2000的时间,而面对T次询问,每次询问只需要( O(1) )的时间就可以回答,是不是超级方便!

代码分享


read是读入优化函数,然后处理询问的时候用了一个三目运算符,其余的就基本上没有难于理解的地方了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
#define R register
#define I inline
template<class T>void read(T &x) {
register int c = getchar(), f = 1; x = 0;
while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
int n,m,k,t;
int a[2002][2002],s[2002][2002];
int main(){
read(t);read(k);
a[1][1]=1;
for(register int i=0;i<=2000;i++) a[i][0]=1;
for(register int i=2;i<=2000;i++)
{
for(register int j=1;j<=i;j++)
{
a[i][j]=(a[i-1][j-1]+a[i-1][j])%k;
}
}
for(register int i=1;i<=2000;i++)
{
for(register int j=1;j<=i;j++)
{
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
if(a[i][j]==0) s[i][j]++;
}
s[i][i+1]+=s[i][i];
}
while(t--)
{
read(n);read(m);
m=m>n?n:m;
printf("%d\n",s[n][m]);
}
return 0;
}



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:725.9k