UVA 861 Little Bishops

吴语林

https://www.luogu.org/problemnew/show/UVA861

A bishop is a piece used in the game of chess which can onlymove diagonally from its current position. Two bishops attackeach other if one is on the path of the other. In the figurebelow, the dark squares
represent the reachable locations forbishop B1 from its current position. Bishops B1 and B2 arein attacking position,
while B1 and B3 are not. Bishops B2and B3 are also in non-attacking position.Given two numbers n and k,
determine the number ofways one can put k bishops on an n × n chessboard so thatno two of them are in attacking positions

Input
The input file may contain multiple test cases. Each testcase occupies a single line in the input file and contains twointegers n (1 ≤ n ≤ 8)
and k (0 ≤ k ≤ n2).A test case containing two zeros terminates the input.

Output
For each test case, print a line containing the total number of ways
one can put the given number ofbishops on a chessboard of the given size so that no two of them lie in attacking positions. You maysafely assume that this
number will be less than 1015

Sample Input
8 6
4 4
0 0
Sample Output
5599888
260

admin

楼上WYL好牛呀  做法正确

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. long long n,k,whi[100],bla[100],lw,lb,all=0,f[100][100];
    
14. void init()
    
15. {
    
16.     memset(bla,0,sizeof(bla));
    
17.     memset(whi,0,sizeof(whi));
    
18.     for(int i=1;i<=n;i++)
    
19.         if(i<=n/2)
    
20.                 {
    
21.             whi[i]=2*i-1;
    
22.             bla[i]=2*i;
    
23.         }
    
24.         else
    
25.                 {
    
26.             if(whi[n+1-i]==0)
    
27.                 whi[i]=whi[i-1]+2;
    
28.             else
    
29.                                 whi[i]=whi[n+1-i];
    
30.             bla[i]=bla[n-i];
    
31.         }
    
32. }
    
33. long long suan_bla(int qi)
    
34. {
    
35.         memset(f,0,sizeof(f));
    
36.         if(qi==0)
    
37.                 return 1;
    
38.         f[1][1]=bla[1];
    
39.         for(int i=2;i<=qi;i++)
    
40.                 f[1][i]=0;
    
41.         for(int i=2;i<=lb;i++)
    
42.         {
    
43.                 f[i][1]=f[i-1][1]+bla[i];
    
44.                 for(int j=2;j<=qi;j++)
    
45.                         f[i][j]=f[i-1][j]+max((long long)0,f[i-1][j-1]*(bla[i]-j+1));
    
46.         }
    
47.         return f[lb][qi];
    
48. }
    
49. long long suan_whi(int qi)
    
50. {
    
51.         memset(f,0,sizeof(f));
    
52.         if(qi==0)
    
53.                 return 1;
    
54.         f[1][1]=whi[1];
    
55.         for(int i=2;i<=qi;i++)
    
56.                 f[1][i]=0;
    
57.         for(int i=2;i<=lw;i++)
    
58.         {
    
59.                 f[i][1]=f[i-1][1]+whi[i];
    
60.                 for(int j=2;j<=qi;j++)
    
61.                         f[i][j]=f[i-1][j]+max((long long)0,f[i-1][j-1]*(whi[i]-j+1));
    
62.         }
    
63.         return f[lw][qi];
    
64. }
    
65. int main()
    
66. {
    
67.         scanf("%lld%lld",&n,&k);
    
68.         while(n!=0||k!=0)
    
69.         {
    
70.                 if(n==1)
    
71.                 {
    
72.                         if(k==1||k==0)
    
73.                                 printf("1\n");
    
74.                         else
    
75.                                 printf("0\n");
    
76.                         scanf("%lld%lld",&n,&k);       
    
77.                         continue;
    
78.                 }
    
79.                 all=0;
    
80.                 init();
    
81.             lw=n,lb=n-1;
    
82.             sort(whi+1,whi+lw+1);
    
83.             sort(bla+1,bla+1+lb);               
    
84.             for(int i=0;i<=k;i++)
    
85.                     all+=suan_bla(i)*suan_whi(k-i);
    
86.             printf("%lld\n",all);
    
87.                 scanf("%lld%lld",&n,&k);
    
88.         }
    
89.     return 0;
    
90. }

复制代码

吴语林

详细说明