方程的解數

Time Limit:?15000MS	?	Memory Limit:?128000K
Total Submissions:?7084	?	Accepted:?2431
Case Time Limit:?5000MS

Description

已知一個n元高次方程：?
?
其中：x1, x2,...,xn是未知數，k1,k2,...,kn是系數，p1,p2,...pn是指數。且方程中的所有數均為整數。?
假設未知數1 <= xi <= M, i=1,,,n，求這個方程的整數解的個數。?
1 <= n <= 6；1 <= M <= 150。?
?
方程的整數解的個數小于2³¹。?
★本題中，指數Pi(i=1,2,...,n)均為正整數。?

Input

第1行包含一個整數n。第2行包含一個整數M。第3行到第n+2行，每行包含兩個整數，分別表示ki和pi。兩個整數之間用一個空格隔開。第3行的數據對應i=1，第n+2行的數據對應i=n。

Output

僅一行，包含一個整數，表示方程的整數解的個數。

Sample Input

3 150 1 2 -1 2 1 2

Sample Output

178

解題思路：這道題直接暴搜肯定回TLE，這里用一點點技巧，把n分成兩半，將左邊的n/2個數的所有可能情況放入到哈希表中，那么在枚舉右邊n/2個數時可以直接通過哈希查詢，這樣可以很快的求解。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int MAX = 4000000; struct Hash {int val;int count; }HashTable[MAX]; int n,m,ans; int k[6],p[6]; bool used[MAX];int getpow(int x, int p) { int tmp = 1; while(p) { if(p & 1) tmp *= x; x *= x; p >>= 1; } return tmp; } int searchHash(int s) {int tmp = s;tmp = (tmp % MAX + MAX) % MAX;while(used[tmp] && HashTable[tmp].val != s){tmp++;tmp = (tmp % MAX + MAX) % MAX;}return tmp; }void insert(int s) {int pos = searchHash(s);HashTable[pos].val = s;HashTable[pos].count++;used[pos] = true; }void leftHalf(int d,int s) {if(d == n / 2){insert(s);return;}for(int i = 1; i <= m; i++)leftHalf(d+1,s + k[d] * getpow(i,p[d])); }void rightHalf(int d,int s) {if(d == n){s = -s;int pos = searchHash(s);if(HashTable[pos].val == s)ans += HashTable[pos].count;return;}for(int i = 1; i <= m; i++)rightHalf(d+1,s + k[d] * getpow(i,p[d])); }int main() {scanf("%d%d",&n,&m);for(int i = 0; i < n; i++)scanf("%d%d",&k[i],&p[i]);leftHalf(0,0);rightHalf(n/2,0);printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的poj 1186 方程的解数(线性探测再哈希)的全部內容，希望文章能夠幫你解決所遇到的問題。

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