前言

我只是湊數(shù)的。

---

正題

---

輸入輸出（建議無視）

Input

　　第1行包含一個(gè)整數(shù)n。第2行包含一個(gè)整數(shù)M。第3行到第n+2行，每行包含兩個(gè)整數(shù)，分別表示ki和pi。兩個(gè)整數(shù)之間用一個(gè)空格隔開。第3行的數(shù)據(jù)對(duì)應(yīng)i=1，第n+2行的數(shù)據(jù)對(duì)應(yīng)i=n。

Output

僅一行，包含一個(gè)整數(shù)，表示方程的整數(shù)解的個(gè)數(shù)。

Sample Input

3
150
1 2
-1 2
1 2

Sample Output

178

---

解題思路

聽真正的dalao講的@神奇冪偉，大概就是把方程分成兩半，如：

k1xp11+k2xp22=?k3xp33?k4xp44k1x1p1+k2x2p2=?k3x3p3?k4x4p4
然后用深搜前半段找出第一個(gè)的所有答案存進(jìn)哈希表里（并且記錄出現(xiàn)次數(shù)），然后再搜一次后半段尋找與前半段答案相反的話就算上方案

---

代碼

#include<cstdio> using namespace std; const int maxn=4000037;//哈希個(gè)數(shù) int n,m,hash[maxn],mid,a[7],p[7],num[maxn],S,ans; int abs(int x) {if (x<0) return -x;else return x; }//絕對(duì)值，定位時(shí)使用 int hashmath(int x) {return abs(x)%maxn;}//哈希函數(shù) int locate(int x)//定位用 {int i=0,w=hashmath(x);//哈希函數(shù)while (i<maxn && hash[(w+i)%maxn]!=0 && hash[(w+i)%maxn]!=x)i++;//找到位置return (w+i)%maxn;//返回位置 } void ins(int x)//加入 {int w=locate(x);//定位hash[w]=x;//改變值num[w]++;//記錄出現(xiàn)次數(shù) } bool find(int x)//查找 {int w=locate(x);//位置if (hash[w]==x) return true;//返回else return false; } void dfs(int dep,int sum)//第一次搜 {if (dep>=mid+1){ins(sum);//插入return;}for (int i=1;i<=m;i++){ans=i;for (int j=2;j<=p[dep];j++) ans*=i;//即使x^pans*=a[dep];//得出結(jié)果dfs(dep+1,sum+ans);//搜} } void dfs2(int dep,int sum) {if (dep>=n+1){if (find(-sum)) S+=num[locate(-sum)];//如果找到就記錄return;}for (int i=1;i<=m;i++){ans=i;for (int j=2;j<=p[dep];j++) ans*=i;ans*=a[dep];dfs2(dep+1,sum+ans);} } int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d%d",&a[i],&p[i]);}mid=n/2;//分成兩段dfs(1,0);dfs2(mid+1,0);printf("%d",S); }

總結(jié)

以上是生活随笔為你收集整理的ssl1127-方程的解数【HASH,dfs】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。