基本计数方法系列 uva习题

uva 11538 (排列组合)

主要是推公式nP2 n为有多少个点可以选放两个皇后，行和列的公是显而易见

分别为 n*m*(m-1)  and m*n*(n-1)主要是对角线的公式难出来。先分析一个4*7的棋盘

图上蓝色的均为有m个格子可以选对于这部分可以推出公是(n-m+1)*m*(m-1)

对于彩色的格子则可以看出他是从2-（n-1）的2*∑i*(i-1)

推出公式m*(m-1)*(2*m-4)/3然后就是编程求解了，代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;

//m<=n
inline ll solve(ll m, ll n)
{
    ll row = m*n*(n-1), col = n*m*(m-1), dia = (n-m+1)*m*(m-1)+m*(m-1)*(2*m-4)/3;
    return row+col+2*dia;
}

int main()
{
//    freopen("in.txt", "r", stdin);

    ll m, n;
    while(scanf("%lld%lld", &m, &n)!=EOF)
    {
        if(n==0 && m==0)break;
        ll ans = solve(min(m, n),max(m,n));
        printf("%lld
", ans);
    }
    return 0;
}

 uva 11401 (简单递推)

从1-n中选出三个数组成三角形，有多少种不同的方案。

由于数据较大无法暴力，只能想递推公式了。ans[i]的意义是最长边长为i能有做少种方案。

ans[i] = ans[i-1]+c[i];

下面来讨论c[i]中包含哪些项 设三角形三边为a, b, i(最长边)有a+b>i

由于i固定枚举a可知道当a = 1,2,3,...,i-1时b的方案。正好得出b = 0,1,2...,i-2

这样可得出总的情况b = (i-1)*(i-2)/2但是这样计入了a==b的情况（方案数-(int)(n/2)）

最后由于每种情况都计算了两遍所以直接除以二就是c[i]的正确值了。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define maxn 1001000
using namespace std;

ll ans[maxn];

void init()
{
    ans[3] = 0;
    for(ll i=4; i<1000001; i++){
        ans[i] = ans[i-1] + ((i-1)*(i-2)/2 - (i-1)/2)/2;
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);

    int n;
    init();
    while(scanf("%d", &n)!=EOF){
        if(n<3)break;
        printf("%lld
", ans[n]);
    }
    return 0;
}

 uva 11806 (容斥原理)

很容易想到是容斥原理，但是WA了好多次一直在查原因查不出来，最后无奈用liurujia书上的代码一块块替换，刚换初始化时交上去就ac了。

接下来想了一下初始化哪里错了。一开始我初始化算C(nk)使用公式算的，而书上则使用的递推虽然复杂度一样但是仔细考虑一下发现问题出在了MOD上面。

一旦后一个阶乘足够大则会导致他与前面的阶乘除法出错。所以很无奈我这个初始化貌似不行，然后貌似我能想到的改进方法则是开二维数组初始化jc。这个貌似小题大作了。

还是应该把书上的学会。（我实在是太菜了！）

代码如下： 

//Cheerleader.cpp
//容斥原理
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
#define MOD 1000007
using namespace std;

int T;
ll n, m, k, jc[2000], c[510][510];

//一开始wa的初始化函数
//void init()
//{
//    jc[0] = 1;
//    for(int i=1; i<1000; i++){
//        jc[i] = (jc[i-1]*i)%MOD;
//    }
//}

//inline ll C(ll _n, ll _k)
//{
//    if(_k>_n) return 0;
//    return (jc[_n]/(jc[_n-_k]*jc[_k]))%MOD;
//}

void init()
{
    memset(c, 0, sizeof c);
    c[0][0] = 1;
    for(int i=0; i<510; i++){
        c[i][0] = c[i][i] = 1;
        for(int j=1; j<i; j++){
            c[i][j] = (c[i-1][j]+c[i-1][j-1])%MOD;
        }
    }
}

inline ll C(ll _n, ll _k){return c[_n][_k];}

ll solve()
{
    ll ret = C(n*m,k);  //总的情况
    ret = ret + 4*MOD - 2*C((n-1)*m,k)-2*C((m-1)*n,k);  //有一行或一列不选
    ret %= MOD;
    ret = ret + 4*C((n-1)*(m-1),k) + C(n*(m-2),k) + C((n-2)*m,k); //两行或两列或一行一列不选
    ret %= MOD;
    ret = ret + 4*MOD - 2*C((n-1)*(m-2),k)-2*C((m-1)*(n-2),k);
    ret %= MOD;
    ret = ret + C((n-2)*(m-2),k);               //两行两列都不选
    ret %= MOD;
    return ret;
}

int main()
{
//    freopen("in.txt" ,"r", stdin);

    init();
    scanf("%d", &T);
    for(int cnt=1; cnt<=T; cnt++){
        scanf("%lld%lld%lld", &m, &n, &k);
        ll ans = solve();
        printf("Case %d: %lld
" ,cnt, ans);
    }
    return 0;
}