1. 题目

传送门= ̄ω ̄=

2. 题解

首先如果暴搜,1506的复杂度显然要gg
那么就中途相遇即可。
首先移项,把右边的n/2个项移动到等号右边,这些项的系数全部都乘以-1就行了
然后用dfs枚举等号左边n/2个未知数的值,复杂度1503。把搜出来的等号左边的项的总和保存在哈希表里。
再dfs枚举等号右边n/2个未知数的值,复杂度也是1503。每次搜出一个总和就去哈希表里查这个值出现了多少次,加到答案里。
于是问题就解决了。
然而丧心病狂的出题人居然卡内存。。。
用mapMLE,用pb_dsMLE,用vector搞链式哈希,哈希大小大了MLE,小了TLE
呵呵
我就是不手写链表!
最后灵机一动。

窝搞双特征值哈希!
就是搞两个不同的素数当作模数,哈希表搞二位的,第一维是查找的值对第一个素数取模的结果,第二维是查找的值对第二个素数取模的结果。
这两个素数都不用太大,我选的是233和1523。
然后解决冲突是用的链式哈希。
然后就过了

代码:

#include <bits/stdc++.h>
#define M1 (233)
#define M2 (1523)
using namespace std;
typedef pair<int,int> PII;
int n,m,mid,k[10],p[10],ans;
vector<PII> htab[M1][M2];
void add(int a)
{
    int r1=(a%M1+M1)%M1,r2=(a%M2+M2)%M2;
    for(vector<PII>::iterator i=htab[r1][r2].begin();i!=htab[r1][r2].end();i++)
        if(i->first==a){i->second++;return;}
    htab[r1][r2].push_back(make_pair(a,1));
}
int hfind(int a)
{
    int r1=(a%M1+M1)%M1,r2=(a%M2+M2)%M2;
    for(vector<PII>::iterator i=htab[r1][r2].begin();i!=htab[r1][r2].end();i++)
        if(i->first==a)return i->second;
    return 0;
}
void dfs1(int a,int tot)
{
    if(a>mid){add(-tot);return;}
    for(int i=1;i<=m;i++)dfs1(a+1,tot+k[a]*pow(i,p[a]));
}
void dfs2(int a,int tot)
{
    if(a>n){ans+=hfind(tot);return;}
    for(int i=1;i<=m;i++)dfs2(a+1,tot+k[a]*pow(i,p[a]));
}
int main()
{
    scanf("%d%d",&n,&m),mid=n>>1;
    for(int i=1;i<=n;i++)scanf("%d%d",&k[i],&p[i]);
    dfs1(1,0),dfs2(mid+1,0),printf("%d\n",ans);
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *