有趣的数


一、 题目描述

题目链接

描述

二、分析

  • 题目中有三个要求,可以将0和1看作第一类,2和3看作第一类,然后就是排列组合问题。

  • 首先设第一类数个数为 k ,则第二类数个数为 n - kk的范围为:[2 ,n - 2]

  • 从k个位置中选取第一类的位置,因为最高为不能为0,所以第一类的可能位置有 :

  • 之后具体分第一类中0和1的位置,因为 01的前面且必须有一个,所以第一类里面的情况有 k-1 种:01111…11(一个0和k-1个1) 和00111…111(两个0和k-2个1) 到 0000…0001 (k-1个0和共1个1)。

  • 同理第二类数字中的位置情况: n - k - 1种。

  • 综上所述,方案数为:


三、代码

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
const int N = 1010,mod = 1e9+7;
int n,re,t,c[N][N];
//组合数数组的初始化
void init(){
for(int i = 0;i<= n;i++){
for(int j = 0;j<= i;j++){
if(!j) c[i][j] = 1;
else{
c[i][j] = (c[i-1][j-1] + c[i-1][j])%mod;
}
}
}
}
int main(){
cin>>n;
init();
for(int i = 2;i <= n-2 ; i++){
//因为可能超范围,所以转换为long,相乘的中间也要模一下
re =( re + (ll)c[n-1][i]*(i-1)%mod *(n-1-i) )%mod;
}
cout<<re<<endl;
return 0;
}
0%