组合数学小刷

今天状态糟糕，但这些题还挺有趣。

下面的图片更有趣，音乐亦然。 清明节想播放一首清明雨上的，奈何无版权。

img

Chess Queen

You probably know how the game of chess is played and how chess queen operates. Two chess queens are in attacking position when they are on same row, column or diagonal of a chess board. Suppose two such chess queens (one black and the other white) are placed on (2 × 2) chess board. They can be in attacking positions in 12 ways, these are shown in the picture below:

Figure: in a (2 × 2) chessboard 2 queens can be in attacking position in 12 ways Given an (N × M) board you will have to decide in how many ways 2 queens can be in attacking position in that. Input Input file can contain up to 5000 lines of inputs. Each line contains two non-negative integers which denote the value of M and N (0 < M, N ≤ 106 ) respectively. Input is terminated by a line containing two zeroes. These two zeroes need not be processed. Output For each line of input produce one line of output. This line contains an integer which denotes in how many ways two queens can be in attacking position in an (M × N) board, where the values of M and N came from the input. All output values will fit in 64-bit signed integer. Sample Input 2 2 100 223 2300 1000 0 0 Sample Output 12 10907100 11514134000

1.同一行

在同一行的两个皇后，它们放置的方案是从 \(n\) 列中任选两列进行放置。由于两个皇后颜色不同，所以方案数是 \(A^2_n\) ，而不是 \(C^2_n\) 。 由于一共有 \(m\) 行，根据乘法原理，同一行的总方案数为 \[ A^2_n * m = \frac{n!}{(n-2)!} * m = n(n - 1) * m \]

2.同一列

同理，可以得到在同一列的方案数量为 \[A^2_m * n = \frac{m!}{(m-2)!} * m = m(m - 1) * n\]

3.同一斜线

有了前两步的分析 同一斜线上的情况就好分析了， 先假设某一条斜线长度为 \(l\) ，根据前面的分析，皇后在这一条斜线上互相攻击的方案数就是 \[ A^2_l = \frac{l!}{(l-2)!} = l(l - 1) \] 那么只需枚举所有斜线长度，答案加上对应的方案数就行了。画图寻找规律可以发现对于 \(m × n\) 的棋盘，当 \(n>m\) 时，它的所有斜线长度分别为 \[ 1,2,3 \dots ,m - 1,\underbrace{m,m\dots,m}_{n - m + 1},m - 1,\dots1 \]

当 \(m>n\) 时，只需要在计算前交换 \(m,n\) 即可。

当然，对角线有两个方向，结果要乘以 \(2\)。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
signed main()
{
ios;
//题意就是同行同列还有同对角线
//同行同列比较容易
int n,m;
while(cin>>m>>n)
{
if(m==0&&n==0)
{
    break;
}
if(m>n)
{
    swap(n,m);
}
int ans=0;
ans+=m*(m-1)*n;
ans+=n*(n-1)*m;
rep(i,1,m-1)
{
ans+=2*2*i*(i-1);
}
rep(i,1,n-m+1)
{
    ans+=2*m*(m-1);
}
cout<<ans<<'\n';
}
return 0;
}

Triangle counting

题意

求1到n长度的n根棍子（3≤n≤1000000）能组成多少不同三角形。

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<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=1e6+100;
int dp[N];
signed main()
{
//给定n根要求计算组成多少个三角形
//假设三条边x,y,z;
//z+y>x(x为最长)
//假设x已经固定住
//x-z>y,有x-z<y<x
//z=1,无解
//z=2,1解，x-1
//z=x-1,z-2解答
//共有(x-2)(x-1)/2个解答
//z可能等于y
//因此需要剔除
//(x+1)/2-(x-1)
//共有(x-2)/2种
dp[1]=dp[2]=dp[3]=0;
rep(i,4,N)
{
    dp[i]=dp[i-1]+(i-2)*(i-2)/4;
}
int n;
while(cin>>n)
{
    if(n<3)
    {
        break;
    }
    cout<<dp[n]<<'\n';
}

    return 0;
}

How Many O's?

求[n, m]之间包含0的数字的个数

我们举例 n = 25789 对于8这位，让其为0对答案的贡献是 （0~257）（0~9）,假设是 n = 25709 那么让这位为0的答案贡献是 （0~256） （0~9） + （257）* （0~9）

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=1e6+100;
int f(int shu )
{
    if(shu<0)
    {
        return 0;
    }
    int x=1;
    int r=0;
    int ans=1;
    while(shu>=10)
    {
int now=shu%10;
shu/=10;
if(now)
{
    ans+=shu*x;
}
else
{
    ans+=(shu-1)*x+r+1;
}
r=r+now*x;
x*=10;
    }
return ans;
}
signed main()
{
    ios;
    int n,m;
    while(cin>>n>>m)
    {
        if(n==-1&&m==-1)
        {
            return 0;
        }
        cout<<f(m)-f(n-1)<<'\n';
    }

}

Supermean

UVa 10883 Supermean 题解 - 洛谷专栏 (luogu.com.cn)

超级平均数，即平均数的平均数。假定有一个数列 \(s_{1\cdots n}\)，那么我们对 \(s\) 两两求平均数，而后对 \(s\) 两两求平均数的结果两两求平均数，……，直到只剩一个数。输出这个数。

题目思路

最烂的方式即模拟算法，复杂度 \(\mathrm O(n^2)\)。弃疗。

我们可以手动模拟一下 \(n=1,2,3,4\) 时的情形（其中 \(O\) 代表答案）：

\[n=1,O=a_1\] \[n=2,O=\frac{1}{2}(a_1+a_2)\] \[n=3,O=\frac{1}{4}(a_1+2a_2+a_3)\] \[n=4,O=\frac{1}{8}(a_1+3a_2+3a_3+a_4)\]

那么系数就是二项式定理给出的三角形

\[1\] \[1\ 1\] \[1\ 2\ 1\] \[1\ 3\ 3\ 1\]

无疑。

那么，我们就可以改写 \(O\) 的式子：

\[O=\frac{1}{2^{n-1}}\sum_{1\le i\le n}\binom{n-1}{i-1}a_i\]

计算它所需的时间是 \(\mathrm O(n)\)，因为我们可以用

\[\binom{n}{m+1}=\frac{n-m}{m+1}\binom{n}{m}\]

使得组合数与 \(a_k\) 可以同步使用。

> 这是因为， > \[\binom{n}{m}=\frac{n!}{m!(n-m)!}=\frac{(m+1)\times(m+2)\times\cdots\times n}{1\times2\times3\times\cdots\times (n-m)}\] > \[\binom{n}{m+1}=\frac{n!}{(m+1)!(n-m-1)!}=\frac{(m+2)\times\cdots\times n}{1\times2\times3\times\cdots\times (n-m-1)}\] > 这样，我们就可以用手推导出它们的比值 > \[\binom{n}{m+1}\left/\binom{n}{m}=\frac{n-m}{m+1}\right.\]

不幸的是由于 \(n\le 5\times 10^4\)，它的精度非常低，怎么办呢？

参考了几篇题解，他们使用了对数作为提高精度的工具。这里采用符号 \(\mathrm{Pw}(a,b)=a^b\) 来替代部分数学符号，因为把一大串式子写在幂上实在不太好。

那么我们就可以改写原来的式子：

\[=\sum_{1\le i\le n}\binom{n-1}{i-1}\frac{a_i}{2^{n-1}}\] \[=\sum_{1\le i\le n}\mathrm{sgn }\ a_i\mathrm{Pw}\left[2,\log_2\binom{n-1}{i-1}+ \log_2|a_i|-\log_2(n-1)\right]\]

虽然式子很长，但是它使用了对数来保证精度。

当然，随着我们使用对数，我们也得把增长贼快的二项式系数改作如下形式：

\[\log_2\binom{n}{m+1}=\log_2\binom{n}{m}+\log_2\frac{n-m}{m+1}\]

那么我们就可以只计算 \(a\) 的对数并把指数加在答案上就好了。

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=1e6+100;
long double sgn(long double x){
    if(x>0) return 1.0;
    if(x<0) return -1.0;
    return 0.0;
}
void Totoro(int x)
{
    int n;
    cin>>n;
    long double a[50020],ans=0,yanhui=0;
    n--;
    rep(i,0,n)
    {
        cin>>a[i];
        ans+=sgn(a[i])*pow(2.0,yanhui+log2(fabs(a[i]))-n);
        yanhui+=log2((double)(n-i)/(double)(i+1)); 
    }
  cout<<"Case #"<<x<<": "<<LF(3)<<ans<<endl;
}
signed main()
{
    ios;
    //第一次见到对数优化
    //长知识了
    //这个题写出表达式就是直接杨辉三角，但是复杂度不允许
    //于是需要递推
    //然后精度不允许，于是需要进行对数优化
    int t;
    cin>>t;
    int x=0;
    while(t--)
    {
        Totoro(++x);
    }
}

Neon Sign

正难则反

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
const int N=1e3+100;
int  a[N];
signed main()
{
//求颜色相同的
//直接正难则反
//全部三角形很容易
//不同色边的，可以计算出从该点连出的边有多少边颜色不一样
//直接乘法原理÷2即可
ios;
int t;
cin>>t;
while(t--)
{
    int n;
    cin>>n;
    memset(a,0,sizeof a);
    //多测不清就寄
    rep(i,1,n)
    {
        rep(j,i+1,n)
        {
            int c;
            cin>>c;
            if(c==1)
            {
                a[i]++;
                a[j]++;
            }
        }
    }
    int ans=n*(n-1)*(n-2)/6;
    int res=0;C++
    rep(i,1,n)
    {
res+=a[i]*(n-1-a[i]);
    }
    cout<<ans-res/2<<'\n';
}

    return 0;
}