[HNOI2002] Kathy 函数

数位 DP 套路题，求二进制下区间内回文串个数。

设 dp[][][] 表示到第几位时，是否为回文数，去掉前导零后共几位。之后到边界时判断是否为回文数计入贡献。

一开始不知道答案统计要高精，于是后来就自闭了。

#include <cmath>

#include <queue>

#include <cstdio>

#include <cctype>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 350;

int n, num[maxn], tmp[maxn]; char str[maxn], che[maxn][2][maxn];

class Big_integer {

private:

  int len, a[105];

public:

  Big_integer() { memset(a, 0, sizeof a), len = 1; }

  ~Big_integer() {};

  inline bool operator == (const Big_integer &x) const {

    if( this->len != x.len ) return false;

    for(int i = len; i; --i) if( this->a[i] != x.a[i] ) return false;

    return true;

  }

  inline bool operator < (const Big_integer &x) const {

    if( this->len != x.len ) return this->len < x.len;

    for(int i = len; i; --i) if( this->a[i] > x.a[i] ) return false;

    return (*this == x) == false;

  }

  inline bool operator > (const Big_integer &x) const {

    if( this->len != x.len ) return this->len > x.len;

    for(int i = len; i; --i) if( this->a[i] < x.a[i] ) return false;

    return (*this == x) == false;

  }

  inline Big_integer operator = (int x) {

    memset(a, 0, sizeof a), len = 0;

    while( x ) a[++len] = x % 10, x = x / 10;

    return *this;

  }

  inline Big_integer operator + (const Big_integer &x) const {

    Big_integer res;

    res.len = max(this->len, x.len) + 1;

    for(int i = 1; i <= res.len; ++i) {

      res.a[i] = this->a[i] + x.a[i] + res.a[i];

      if( res.a[i] > 9 ) res.a[i + 1] = res.a[i] / 10, res.a[i] = res.a[i] % 10;

    }

    while( res.a[res.len] == 0 && res.len > 1 ) --res.len;

    return res;

  }

  inline Big_integer operator / (const int &x) const {

    Big_integer res;

    res.len = this->len;

    for(int r = 0, i = len; i; --i) res.a[i] = (r * 10 + this->a[i]) / x, r = (r * 10 + this->a[i]) % x;

    while( res.a[res.len] == 0 && res.len > 1 ) --res.len;

    return res;

  }

  inline void read() {

    scanf("%s", str + 1), len = strlen(str + 1);

    for(int i = len; i; --i) a[i] = str[len - i + 1] ^ 48;

  }

  inline void prin() {

    for(int i = len; i; --i) printf("%d", a[i]); printf("\n");

  }

  inline void Transform(int *arr) {

    while( a[len] != 0 ) arr[++n] = a[1] & 1, *this = *this / 2;

  }

} a, dp[maxn][2][maxn];

inline Big_integer Deep_fs(int fir, int pos, int tag, int limit) {

  Big_integer res;

  if( pos < 1 ) return (tag && fir > 0) ? res = 1 : res = 0;

  if( limit == 0 && che[pos][tag][fir] ) return dp[pos][tag][fir];

  for(int i = 0; i <= (limit ? num[pos] : 1); ++i) {

    tmp[pos] = i;

    if( fir == pos && i == 0 ) res = res + Deep_fs(fir - 1, pos - 1, tag, limit && i == num[pos]);

    else res = res + Deep_fs(fir, pos - 1, (tag && pos <= (fir >> 1)) ? tmp[fir - pos + 1] == i : tag, limit && i == num[pos]);

  }

  if( limit == 0 ) dp[pos][tag][fir] = res, che[pos][tag][fir] = 1;

  return res;

}

int main(int argc, char const *argv[])

{

  a.read(), a.Transform(num), Deep_fs(n, n, 1, 1).prin();

  return 0;

}

巴特西

[HNOI2002] Kathy 函数

最新文章

热门文章