题解 | 九倍平方数

可以用dp更快的解决

#include <iostream>
#include <vector>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<string.h>
#include<random>
#include<stack>
#include<list>
#include<deque>
#include<set>
#include<sstream>
#include<bitset>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll MAX = 5001;
ll positive_mod(ll a, ll b) {
    return (a % b + b) % b;
}

void solve(string s) {
    vector<ll> pre(s.size(), 0);
    vector<vector<ll> > dp(s.size() + 2, vector<ll>(9, 0));
    pre[0] = s[0] - '0';
    for (int i = 1; i < s.size(); i++) {
        pre[i] = pre[i - 1] + s[i] - '0';
    }
    ll sum = pre[s.size() - 1];
    if (sum % 9 == 0) {
        cout << "YES\n";
        return;
    }
    for (int j = 0; j < 9; j++) {//注意最开始 的总和mod9要赋值不然一直是0
        if (sum % 9 == j) dp[0][j]++;
    }


    for (int i = 0; i < s.size(); i++) {
        int x = s[i] - '0';
        if (x * x >= 10||x==0||x==1)//注意把0和1都去掉，不知道为啥不把0，1放到这里讨论为啥过不了
            for (int j = 0; j < 9; j++) {
                dp[i + 1][j] = dp[i][j];
            } else {
            for (int j = 0; j < 9; j++) {
                dp[i + 1][j] = dp[i + 1][j] + dp[i][j];
                dp[i + 1][(j + x * x - x) % 9] = dp[i + 1][(j + x * x - x) % 9] + dp[i][j];
            	//转移方程如果对当前修改后dp[i+1][(j+x*x-x)%9]的方案要经过dp[i][j]累加即可
			  	//dp[i+1][j] = dp[i+1][j] + dp[i][j]即不修改。
			}
            if (dp[i + 1][0]) {
                cout << "YES\n";
                return;
            }
        }
    }
    if (dp[s.size()][0]) cout << "YES\n";
    else
        cout << "NO\n";
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        solve(s);
    }
}

// 64 位输出请用 printf("%lld")