P1497 木牛流马 题解

· · 题解

[P1497 木牛流马] 题解

推导过程:

当 n = 4,h = 1,c = 1时: 放置木牛流马的个数 情况数 可表示为
1 4\times4 n^2
2 3\times3 (n-1)^2
3 2\times2 (n-2)^2
i (n-i+1)^2 
不能放在同行同列           ——writer

所以总情况数为:

ans = n^2 + (n-1)^2 + ... + (n-i+1)^2
但是以上结论是在\red{颜}\blue{色}互不相同的情况才下成立 所以要再减去重复的部分: h 重复的情况数
0 4\times3\times2\times1=4!
1 4\times3\times2=\frac{4!}{1!}
2 4\times3=\frac{4!}{2!}
3 4=\frac{4!}{3!}

所以

ans=\frac{n^2+(n-1)^2+...+(n-i+1)^2}{c_1!\times c_2!\times c_3!\times...\times c_h!}

上代码:

#include <iostream>//数学 
using namespace std;
int main(){
    int n,k,h; cin >> n >> k >> h;
    long long ans = 1,c = 0;
    for(int i = 1;i <= k;i++)
        ans *= (n-i+1) * (n-i+1);
    for(int i = 1;i <= h;i++){
        cin >> c;
        for(int j = 1;j <= c;j++) ans /= j;
    }
    cout << ans;
    return 0;
}
end