[NOI 2001] 方程的解数

知识点

折半搜索、排序、组合计数

解题思路

把变量分成两组，每组最多3个。预先算好各变量在1到m的项值，枚举每组所有和存入数组，排序后一边从小到大、一边从大到小匹配和为0的两段相等值，贡献为两段长度乘积。空半组的和为0。

正确性说明

每个完整解唯一对应左右两半的两个赋值，其和相反当且仅当原方程成立。每个半组和的重复次数等于实现它的赋值数量，乘积恰为这对和产生的完整解数；双指针按大小跳过不可能匹配的值，最终覆盖全部解。

易错点

n可能1，空组仍有一种空赋值；指数可能很大但m=1或系数0使项值仍有界，快速幂且0系数直接跳过；中间计数用64位；题面保证总绝对值和及答案上界。

复杂度

时间O(nm log p+m^ceil(n/2) log(m^ceil(n/2)))，空间O(m^ceil(n/2))，最多每边150³项。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
long long power(long long x,int p){long long r=1;while(p){if(p&1)r*=x;p>>=1;if(p)x*=x;}return r;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<vector<long long>>v(n,vector<long long>(m));for(int i=0;i<n;i++){long long k;int p;cin>>k>>p;for(int j=1;j<=m;j++)v[i][j-1]=k? k*power(j,p):0;}int mid=n/2;auto enumerate=[&](int l,int r){vector<long long>a(1,0);for(int i=l;i<r;i++){vector<long long>b;b.reserve(a.size()*m);for(long long s:a)for(long long x:v[i])b.push_back(s+x);a.swap(b);}sort(a.begin(),a.end());return a;};auto a=enumerate(0,mid),b=enumerate(mid,n);long long i=0,j=(long long)b.size()-1,ans=0;while(i<(long long)a.size()&&j>=0){long long s=a[i]+b[j];if(s<0){++i;continue;}if(s>0){--j;continue;}long long u=i,w=j;while(i<(long long)a.size()&&a[i]==a[u])++i;while(j>=0&&b[j]==b[w])--j;ans+=(i-u)*(w-j);}cout<<ans<<'\n';}