當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

UESTC 1851 Kings on a Chessboard

發布時間：2024/6/14 编程问答 33 豆豆

生活随笔收集整理的這篇文章主要介紹了 UESTC 1851 Kings on a Chessboard 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

狀壓DP。。。

Kings on a Chessboard

Time Limit:?10000msMemory Limit:?65535KBThis problem will be judged on UESTC. Original ID:?1851
64-bit integer IO format:?%lld????? Java class name:?MainPrev?Submit?Status?Statistics?Discuss?NextFont Size:?+?-Type:??None?Graph Theory?????2-SAT?????Articulation/Bridge/Biconnected Component?????Cycles/Topological Sorting/Strongly Connected Component?????Shortest Path?????????Bellman Ford?????????Dijkstra/Floyd Warshall?????Euler Trail/Circuit?????Heavy-Light Decomposition?????Minimum Spanning Tree?????Stable Marriage Problem?????Trees?????Directed Minimum Spanning Tree?????Flow/Matching?????????Graph Matching?????????????Bipartite Matching?????????????Hopcroft–Karp Bipartite Matching?????????????Weighted Bipartite Matching/Hungarian Algorithm?????????Flow?????????????Max Flow/Min Cut?????????????Min Cost Max Flow?DFS-like?????Backtracking with Pruning/Branch and Bound?????Basic Recursion?????IDA* Search?????Parsing/Grammar?????Breadth First Search/Depth First Search?????Advanced Search Techniques?????????Binary Search/Bisection?????????Ternary Search?Geometry?????Basic Geometry?????Computational Geometry?????Convex Hull?????Pick's Theorem?Game Theory?????Green Hackenbush/Colon Principle/Fusion Principle?????Nim?????Sprague-Grundy Number?Matrix?????Gaussian Elimination?????Matrix Exponentiation?Data Structures?????Basic Data Structures?????Binary Indexed Tree?????Binary Search Tree?????Hashing?????Orthogonal Range Search?????Range Minimum Query/Lowest Common Ancestor?????Segment Tree/Interval Tree?????Trie Tree?????Sorting?????Disjoint Set?String?????Aho Corasick?????Knuth-Morris-Pratt?????Suffix Array/Suffix Tree?Math?????Basic Math?????Big Integer Arithmetic?????Number Theory?????????Chinese Remainder Theorem?????????Extended Euclid?????????Inclusion/Exclusion?????????Modular Arithmetic?????Combinatorics?????????Group Theory/Burnside's lemma?????????Counting?????Probability/Expected Value?Others?????Tricky?????Hardest?????Unusual?????Brute Force?????Implementation?????Constructive Algorithms?????Two Pointer?????Bitmask?????Beginner?????Discrete Logarithm/Shank's Baby-step Giant-step Algorithm?????Greedy?????Divide and Conquer?Dynamic Programming? ? ?? ?? ?? ?? ???Tag it!

You are given a chessboard of size x * y and k identical kings, and are asked to place all the kings on the board such that no two kings can attack each other. Two kings can attack each other if they are horizontally, vertically or diagonally adjacent.
Write a computer program that calculates the number of possible arrangements of the k kings on the given chessboard. Since the number of feasible arrangements may be large, reduce the number modulo 1,000,000,007.

Input

The first line of the input consists of a single integer T, the number of test cases. Each of the following T lines consists of three integers x; y and k,separated by one space.

0 < T <= 50
2 <= x; y <= 15
1 <= k <= x*y

Output

For each test case, output the number of possibilities modulo 1,000,000,007.

Sample Input

4
8 8 1
7 7 16
7 7 7
3 7 15

Sample Output

64
1
2484382
0

Source

IDI Open 2013 Programming Contest

#include?<iostream>
#include?<cstdio>
#include?<cstring>

using?namespace?std;

const?int?MOD=1000000007;

inline?bool?legal(int?x,int?y)?{return?x&y;}
long?long?int?dp[16][1600][250];
int?r,c,nums,state[1600],people[1600],kth;

bool?isOK(int?xia,int?shang)
{
????int?x=state[xia],y=state[shang];
????if(legal(x,y))?return?false;
????if(legal(x<<1,y)||legal(x>>1,y))?return?false;
????return?true;
}

int?main()
{
????int?t;
????scanf("%d",&t);
????while(t--)
????{
????????memset(dp,0,sizeof(dp));
????????scanf("%d%d%d",&r,&c,&kth);
????????if(kth>(r+1)/2*(c+1)/2)
????????{
????????????puts("0");
????????????continue;
????????}
????????if(c>r)?swap(r,c);
????????///zuangtai
????????nums=0;
????????memset(state,0,sizeof(state));
????????memset(people,0,sizeof(people));
????????for(int?i=0;i<(1<<c);i++)
????????{
????????????if(legal(i,i<<1)||legal(i,i>>1))?continue;
????????????state[nums]=i;
????????????int?k=i;
????????????while(k)
????????????{
????????????????if(k&1)?people[nums]++;
????????????????k=k>>1;
????????????}
????????????nums++;
????????}
????????///the?firstline
????????for(int?i=0;i<nums;i++)
????????{
????????????dp[1][people]=1;
????????}
????????for(int?i=2;i<=r;i++)
????????{
????????????for(int?j=0;j<nums;j++)
????????????{
????????????????for(int?k=0;k<nums;k++)
????????????????{
????????????????????if(!isOK(j,k))?continue;
????????????????????for(int?l=people[k];l<250;l++)
????????????????????{
????????????????????????if(l+people[j]<250)
????????????????????????????dp[j][l+people[j]]=(dp[j][l+people[j]]+dp[i-1][k][l])%MOD;
????????????????????}
????????????????}
????????????}
????????}
????????long?long?int?ans=0;
????????for(int?j=0;j<nums;j++)
????????{
????????????ans=(ans+dp[j][kth])%MOD;
????????}
????????printf("%lld\n",ans%MOD);
????}
????return?0;
}

* This source code was highlighted by?YcdoiT. ( style: Codeblocks )

轉載于:https://www.cnblogs.com/CKboss/p/3350829.html

總結

以上是生活随笔為你收集整理的UESTC 1851 Kings on a Chessboard的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。