SSL_1227_方程的解数_dfs_hash

发布于 2019-04-24  9 次阅读


题目大意

给定n个系数和次方数,使x在给定的范围内,求方程等于0的解的个数
这里写图片描述

思路

这题可以吧方程分成两个部分进行搜索,将前一个部分得出的数存入hash表中,然后在搜索后半部分时将结果的相反数在hash表中查找,如果找到的话,ans++;
O(n^3)
某些神奇的数据会爆炸。。。

#include 
#include 
#include 
#include 
#define M 4000037
using namespace std;
int h[M+1][3];
int mi[2000][500],ll;
int n,m;
long long ans,a[700][3];
int insert(int x)
{
    int y=x;
    if (y<0) y=-x;
    int i=y%M;
    while (h[i][1]!=0&&h[i][1]!=x) i=i%M+1;
    h[i][1]=x;
    h[i][2]=h[i][2]+1;
}
int find(int x)
{
    int y=x;
    if (y<0) y=-x;
    int i=y%M;
     if (i==0)
    {
        int k;
    }
    while (h[i][1]!=0&&h[i][1]!=x) i=i%M+1;
    ll=i;
}
int dfs(int dep,int o)
{
    if (dep>n/2)
    {
        insert(o);
        return 0;
    }
    for (int i=1;i<=m;i++)
        dfs(dep+1,o+a[dep][1]*mi[i][a[dep][2]]);
}
int dfs1(int dep,int o)
{
    if (dep>n)
    {
        int p=0;
        ll=find(o*-1);
        if (h[ll][1]==o*-1) 
        {
            ans=ans+h[ll][2];
        }
        return 0;
    }
    for (int i=1;i<=m;i++)
        dfs1(dep+1,o+a[dep][1]*mi[i][a[dep][2]]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%I64d%I64d",&a[i][1],&a[i][2]);   
    for (int i=1;i<=30;i++)
        mi[1][i]=1;
    for (int i=2;i<=m;i++)
    {
        mi[i][0]=1;
        for (int j=1;j<=(log(0x7fffffff)/log(i));j++)
            mi[i][j]=mi[i][j-1]*i;
    } 
    dfs(1,0);
    dfs1((n/2)+1,0);
    long long xx=ans;
    printf("%I64d",xx);
}
]]>