组合数板子

最近打了两场比赛,都有组合数的题目,第一次是真的把我wa到死,今天牛客又来一次,不过我还是弄对了,在这里放个板子吧

首先呢,我先把我校校赛题的C放上来
http://oj.jxust.edu.cn/problem?id=2387

题目描述
A和B在玩石头剪刀布的游戏(0代表石头,1代表剪刀,2代表布),他们进行了n场游戏,现在A知道B每场的情况,赢一场得一分,输和平不得分,问A最终得分为S的情况有多少种?
输入
第一行输入N和S,N表示进行N场游戏,S表示A的得分。
第二行输入N个数(0,1,2),表示B每场的情况。
输出
输出有多少中情况使的A得分为S,数字很大,需要对答案取模
样例输入
3 1
0 1 2
样例输出
12
提示
费马小定理

这个题公式还是很好弄出来的,结果很显然和第二行输入没什么关系,公式应该是
C(S,N)2^(N-S)%MOD*
一开始嘛…暴力,肯定是错了
然后说是费马小定理,除法取模改了好一阵也没好,最后这个代码AC了

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
//[费马小定理介绍](https://www.cnblogs.com/ECJTUACM-873284962/p/6847672.html "费马小定理的介绍")
#include <iostream>
#define int long long
using namespace std;
const int maxn=1e9+7;
int quickw(int a,int b,int mod){
if(b==0)return 1;
int x=quickw(a,b/2,mod);
int ans=x*x%mod;
if(b%2==1)ans=ans*a%mod;
return ans;
}
int c(int n,int s){
if(s==0)return 1;
else return ((n-s+1)/s)*c(n,s-1);
}
signed main(){
int a,b;
cin>>a>>b;
for(int i=0;i<a;i++){
int y;
cin>>y;
}
int res,cnt;
if(a<b)cout<<"0"<<endl;
else{
res=quickw(2,a-b,maxn);
int aa=1,bb=1;
for(int i=a;i>=a-b+1;i--){
aa*=i;
aa%=maxn;
}
res*=aa;
res%=maxn;
for(int i=b;i>=1;i--){
bb*=quickw(i,maxn-2,maxn);
bb%=maxn;
}
//cout<<bb<<endl;
cnt=(res*bb)%maxn;
cout<<cnt<<endl;
}
return 0;
}

另一个组合数的题是这个:
https://ac.nowcoder.com/acm/contest/553/D

链接:https://ac.nowcoder.com/acm/contest/553/D
来源:牛客网

Chino的数学很差,因此Cocoa非常担心。今天,Cocoa要教Chino解不定方程。
众所周知,不定方程的解有0个或者若干个。
给出方程:

Cocoa想知道这个不定方程的正整数解和非负整数解各有几个。
题目对Chino来说太难啦,你能帮一帮Chino吗?
输入描述:

两个正整数m, n

输出描述:

题目要求的答案,即正整数解的个数和非负整数解的个数 。由于答案可能会很大,你只需要输出答案 mod(109 + 7) 即可。

示例1
输入
复制

4 7

输出
复制

20 120

这个和概率论有点关系,第一个数就是C(m-1,n-1)
第二个数是C(m-1,n+m-1)
这里我用的就是模板
AC 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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int maxn=3e6+6;
int jc[maxn]={1,1};
void init(){
for(int i=2;i<maxn;i++){
jc[i]=jc[i-1]*i%mod;
}
}
int quickw(int a,int b,int mod){
int ans=1;
while(b){
if(b&1){
ans=ans*a%mod;
}
a=a*a%mod;
b>>=1;
}
return ans;
}
int niyuan(int a,int b){
return quickw(a,b-2,b);
}
int C(int a,int b){
return jc[a]*niyuan(jc[b],mod)%mod*niyuan(jc[a-b],mod)%mod;
}
signed main(){
int m,n;
cin>>m>>n;
init();
int res,cnt;
res=C(n-1,m-1)%mod;
cnt=C(n+m-1,m-1)%mod;
cout<<res%mod<<" "<<cnt%mod<<endl;
return 0;
}
//这里还有些别的求组合数的方法
//除法取模板子[https://blog.csdn.net/arrowlll/article/details/52629448](https://blog.csdn.net/arrowlll/article/details/52629448)

板子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int jc[maxn]={1,1};
void init(){
for(int i=2;i<maxn;i++){
jc[i]=jc[i-1]*i%mod;
}
}
int quickw(int a,int b,int mod){
int ans=1;
while(b){
if(b&1){
ans=ans*a%mod;
}
a=a*a%mod;
b>>=1;
}
return ans;
}
int niyuan(int a,int b){
return quickw(a,b-2,b);
}
int C(int a,int b){
return jc[a]*niyuan(jc[b],mod)%mod*niyuan(jc[a-b],mod)%mod;
}

放完板子之后放一下这两场比赛别的题:

JXUSTOJ:
2386
http://oj.jxust.edu.cn/problem?id=2386
题目描述
这是一道签到提,最近在学信息隐藏,对初始图像先做n次猫脸变化使其像素的分布变成伪随机数,以达到三层安全中的第一层
先定义函数f(x,y)表示位于x,y位置的像素值,猫脸变化执行如下过程
变换后的图像的x1与y1的像素值用原图像x,y的像素值填充,(x1,y1)与(x2,y2)的关系满足如下矩阵
|x1|=|1 1||x|
|y1| |1 2||y|
其中的2阶矩阵就是猫脸变换矩阵A
A的1次方= |1 1| A的2次方=|2 3| A的3次方=|5 8|
|1 2| |3 5| |8 13|
输入
第一行输入T表示有T组数据,下面T行,每行输入一个数字ni(1<=i<=T)
范围1<=T<=1000 1<=Ni<=1000000
输出
输出T行,每行输出A的ni次方,格式如样例,数据非常大所以要对10^8+7 取模
样例输入
3
1
2
3
样例输出
1 1 1 2
2 3 3 5
5 8 8 13

矩阵快速幂板子

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
样例输入

3
1
2
3

样例输出

1 1 1 2
2 3 3 5
5 8 8 13
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;
const ll maxn=1e8+7;
struct map{
ll m[2][2];
map(){
memset(m,0,sizeof(m));
}
};
map ans;
map mul(map &a,map &b)
{
map c;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%maxn;
return c;
}
map pow(map a,ll n)
{
map b;
b.m[0][0]=b.m[1][1]=1;
while(n)
{
if(n&1)b=mul(b,a);
a=mul(a,a);
n>>=1;
}
return b;
}
void init(){
ans.m[0][0]=1;
ans.m[0][1]=1;
ans.m[1][0]=1;
ans.m[1][1]=2;
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
init();
while(t--){
int n;
map wyh;
cin>>n;
wyh=pow(ans,n);
if(n==1){
cout<<"1 1 1 2"<<endl;
}
else cout<<wyh.m[0][0]<<" "<<wyh.m[0][1]<<" "<<wyh.m[1][0]<<" "<<wyh.m[1][1]<<endl;

}
return 0;
}

2388
http://oj.jxust.edu.cn/problem?id=2388

题目描述
有M种不同颜色的气球(颜色从1至M表示),现在有一排N个位置,需要往这N个位置中填充一些气球,可填也可不填。求最短的区间长度使的这个区间中包含M种颜色的气球。如果没有则输入-1.
输入
第一行输入N和M,N表示位置长度,M表示气球颜色数量。
(1≤M≤1000,1≤N≤
10
6
)
(1≤M≤1000,1≤N≤106)

第二行输入N个数,第i个数ai表示第i个位置气球的颜色,0表示没填充气球。
(0≤ai≤M)
(0≤ai≤M)
输出
输出符合要求的最短区间长度,没有则输入-1。
样例输入
10 6
1 2 3 4 6 3 0 1 2 5
样例输出
7
提示
样例说明:在[4,10]区间,包含1-6,每种颜色都包含并且区间最短。

贪心,一开始我想用数组解决问题,不知道为什么就是不对,我也放这里吧,可能是我没考虑-1的情况

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e6+6;
int n,m;
int up[maxn],down[maxn];
bool vis[maxn];
struct ball{
int color;
int num;
}pos[maxn];
bool cmp(const ball &a,const ball &b){
if(a.color==b.color)return a.num<b.num;
return a.color<b.color;
}
int main(){
memset(vis,true,sizeof(vis));
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>pos[i].color;
pos[i].num=i;
}
sort(pos,pos+n,cmp);
for(int i=0;i<n;i++){
if(pos[i].color!=0){
int _=pos[i].num;
int zz=i;
while(pos[zz+1].color==pos[zz].color){
_=max(_,pos[zz+1].num);
++zz;
}
if(zz==i){
up[i]=pos[i].num;
continue;
}
int c=i;
i=zz;
for(int j=c;j<=zz;j++)
{
up[j]=_;
}
}
else up[i]=-INF;
}
for(int i=0;i<n;i++){
if(pos[i].color!=0){
int _=pos[i].num;
int zz=i;
while(pos[zz+1].color==pos[zz].color){
_=min(_,pos[zz-1].num);
++zz;
}
if(zz==i){
down[i]=pos[i].num;
continue;
}
int cc=i;
i=zz;
for(int j=cc;j<=zz;j++)
{
down[j]=_;

}
}
else down[i]=INF;
}
int min_up,max_up;
min_up=maxn;
max_up=-maxn;
for(int i=0;i<n;i++){
if(up[i]!=-INF){
min_up=min(min_up,up[i]);
max_up=max(max_up,up[i]);
}
}
int min_down,max_down;
min_down=maxn;
max_down=-maxn;
for(int i=0;i<n;i++){
if(down[i]!=INF){
min_down=min(min_down,down[i]);
max_down=max(max_down,down[i]);
}
}
int resa,resb;
resa=max_up-min_up+1;
resb=max_down-min_down+1;
cout<<min(resa,resb)<<endl;
return 0;
}

还挺长….

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
#include <iostream>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e6+6;
int color[maxn];
int num[2005];
int main(){
memset(num,0,sizeof(num));
int n,m;
int wyh=INF;
int cnt=0;
int from=0;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>color[i];
if(color[i]==0){
continue;
}
if(num[color[i]]==0)cnt++;
num[color[i]]++;
while(!color[from]||num[color[from]]>1){//注意在这里考虑from点为0是from前移
num[color[from]]--;
from++;
}
if(cnt==m)wyh=min(wyh,i-from+1);
}
if(cnt!=m)cout<<"-1"<<endl;
else cout<<wyh<<endl;
return 0;
}

2390
http://oj.jxust.edu.cn/problem?id=2390
提交
题目描述
Carryon最近在带学弟刷题,让学弟们打了一场比赛,一共有n个学弟,第i个人的分数为a[i],现在想要给他们分一些糖果作为奖励。将他们围成一个圈发糖,但是怕他们心里不平衡就制定了一些规则。
1.每个人只能看到旁边人的分数和糖果数
2.分数高的得到的糖果比分数低的多
3.每个人至少一个糖果
现在想用最少的糖果来解决这个问题,请输出最终所需要的糖果数。
输入
第一行输入T表示有多少组;(T <= 100)
每组输入为一个整数n,表示学弟的个数。(0 < n <= 10000)
接下来输入n个an[i],表示他们所得的分数。(0 < an[i] < 100000)
输出
输出所需最少的糖果数
样例输入
2
20
2 2 6 7 7 6 5 4 3 1 3 5 7 9 10 10 12 10 10 10
13
2 3 4 4 5 6 7 6 7 6 5 3 2
样例输出
55
32
提示
样例解释:
对于第一个样例当糖果按下面分则最少
1 1 2 3 6 5 4 3 2 1 2 3 4 5 6 1 2 1 1 2
所以答案为55
对于第二样例当糖果按下面分则最少
1 2 3 1 2 3 4 1 5 4 3 2 1
所以答案为32

我的想法就是写一个while循环,每次找最小的,然后向左右扩散,递增就++;不递增就挺,在更新可选点,找最小的继续扩散。总体是没什么问题,但是就是因为围成一个圈,最后一个和第一个的特判我没办法处理好,所以这题还是WA掉了
先放着代码吧,以后如果万一能改了再更新(咕咕咕

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
样例输入

2
20
2 2 6 7 7 6 5 4 3 1 3 5 7 9 10 10 12 10 10 10
13
2 3 4 4 5 6 7 6 7 6 5 3 2

样例输出

55
32

*/
#include <bits/stdc++.h>
using namespace std;
int a[10020];
bool vis[10020];
int dis[10020];
int n;
int main(){
int t;
cin>>t;
while(t--){
cin>>n;
memset(vis,false,sizeof(vis));
memset(dis,0,sizeof(0));
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int o=0;o<100;o++){
int pos;
int _=100009999;
for(int i=0;i<n;i++){
if(!vis[i]&&a[i]<=_){
_=a[i];
}
}
for(int i=0;i<n;i++){
if(a[i]==_&&!vis[i]){
pos=i;
break;
}
}
//cout<<"pos"<<pos<<endl;
dis[pos]=1;
vis[pos]=true;
for(int i=pos+1;i<n;i++){
if(a[i]>a[i-1]&&vis[i]==false){
dis[i]=dis[i-1]+1;
vis[i]=true;
}
else break;
}
for(int i=pos;i>=0;i--){
if(a[i-1]>a[i]&&vis[i-1]==false){
dis[i-1]=dis[i]+1;
vis[i-1]=true;
//cout<<"i-1"<<" "<<i-1<<endl;
}
else break;
}
}
if(a[n-1]>a[0]&&dis[n-1]<=dis[0]){
dis[n-1]=dis[0]+1;
}
int sum=0;
for(int i=0;i<n;i++){
//cout<<dis[i]<<" ";
sum+=dis[i];
}
cout<<sum<<endl;
}
}

西工大程序设计竞赛复现
比赛链接:
https://ac.nowcoder.com/acm/contest/553#question
A:
挺烦的其实,我用C++写了之后精度有点问题,样例的1/3直接判0了,就改成PY写了一波,WA了几次,最后发现我2*a忘记加()了,艹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math
def d(x0,y0,x1,y1):
return math.sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0))
x0,y0,r,x1,y1,y2=map(int,input().split());
h=(y1-y2)/x1
b=y2-y0
a=1+h*h
bb=2*b*h-2*x0
c=x0*x0+b*b-r*r
der=bb*bb-4*a*c
cnm=math.sqrt(der)
xx1=(cnm-bb)/(2*a)
xx2=(-bb-cnm)/(2*a)
yy1=h*xx1+y2;
yy2=h*xx2+y2;
len1=d(xx1,yy1,x1,y1);
len2=d(xx2,yy2,x1,y1);
len=len1*len2
print(int(len))

B
签到题,但我一开始写莽了 WA了好几次

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;
int ans=0;
while(n!=0){
if(n%2!=0&&n!=1)n++;
n/=2;
ans++;
}
cout<<ans-1<<endl;
return 0;
}

C:
就是上面那个组合数的板子

其他的都没做,但是我感觉F我应该能做出来
先把题目放在 回头补

F:
https://ac.nowcoder.com/acm/contest/553/F

总感觉还有啥要写的…但是又忘了,想起来再写把
感觉自己现在更博客写题目都是真的懒

晚风。
coswindy

-------------本文结束感谢您的阅读-------------