题解 | 九倍平方数

母函数，注意n最大是1e5所以可以用bitset二进制优化母函数标记我们想要找到我们经过x^2-x所有要的可能，侥幸能过

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bitset<900001> bit;
void setBit(map<ll,ll> mp){		//母函数标记当前数字是否经过变化x^2-x可达
    bit[0]=1;
    for(auto it : mp){
        int cnt = it.second;
        for(int i=1;cnt>0;i<<=1){
            int ma = min(cnt,i);
            int take = ma*it.first;
            bit |= (bit<<take);
            cnt-=i; 
        }
    }
}
void solve(string s){
    map<ll,ll> mp;
    vector<ll> pre(s.size()+1,0);
    pre[1] = s[1]-'0';
    for(int i=2;i<s.size();i++){
        pre[i] = pre[i-1]+s[i]-'0';
    }
    if(pre[s.size()-1]%9==0){
        cout<<"YES\n";
        return;
    }
    ll res = pre[s.size()-1]%9;
    ll need = 9-res;
    ll sum = 0;
    for(int i=1;i<s.size();i++){
        int x = s[i]-'0';
        sum+=x;
        if(x==1||x==0) continue;//剪枝
        if(x*x>=10) continue;
        sum+=x*x-x;
        mp[(x*x-x)%9]++;
    }
    if(mp.count(need)){
        cout<<"YES\n";
        return ;
    }
    setBit(mp);
    for(int i=1;i<sum;i++){
        if(bit[i]&&(i+res)%9==0){//如果有匹配输出YES
            cout<<"YES\n";
            return ;
        }
    }
    cout<<"NO\n";

}


int main() {
    int t;
    cin>>t;
    while(t--){
        string s = "0";
        bit.reset();
        cin>>s;
        reverse(s.begin(),s.end());
        s+='0';
        reverse(s.begin(),s.end());
        solve(s);
    }
}
// 64 位输出请用 printf("%lld")