Kattis - 广义递归函数WA

Question

我一直在Kattis here上拼命地坚持这个问题。基本思想是为您提供有效的两个变量递归函数的通用公式，然后给出该公式，您将在各种输入处评估此函数的函数。我已经拖过这个问题超过一个小时，我想知道是否有人能指出我正确的方向（或反例）我的答案是错误的。我使用的代码给我一个错误的答案判决如下所示。

    #include<bits/stdc++.h>
    using namespace std; 
    long long dp[105][105];
    int a[25];
    int b[25];
    long long rec(int x_in, int y_in, int coeffs, long long c) {
      if(dp[x_in][y_in]!=-1){
        return dp[x_in][y_in];
      }
      else {
        long long ans = c;
        for(int i=0; i<coeffs; ++i) {
          int x_cell = max(0, x_in-a[i]);
          int y_cell = max(0, y_in-b[i]);
          ans+=rec(x_cell, y_cell, coeffs, c);
        }
        dp[x_in][y_in] = ans;
        return dp[x_in][y_in];
      }
    }

    int main() {
      int n;
      scanf("%d", &n);
      string ex;
      getline(cin, ex);
      for(int caseno=0; caseno<n; ++caseno) {
        memset(dp, -1, sizeof(dp));
        if(caseno>0) printf("\n");
        string coeffs_list;
        getline(cin, coeffs_list);
        int pairs = 0;
        long long c, d;
        char * dup = strdup(coeffs_list.c_str());
        char * token = strtok(dup, " ") ;
        while(token != NULL){
            a[pairs] = atoi(token);
            token = strtok(NULL, " ") ;
            b[pairs] = atoi(token);
            token = strtok(NULL, " ") ;
            pairs++;
        }
        free(dup);
        c= (long long) a[pairs-1];
        d = (long long) b[pairs-1];
        pairs--;
        dp[0][0] = d;
        for(int i=1; i<105; ++i) {dp[0][i] = d; dp[i][0]=d;}
        string inputs;
        getline(cin, inputs);
        int x_i, y_i;
        char * dup2 = strdup(inputs.c_str());
        char * token2 = strtok(dup2, " ") ;
        while(token2 != NULL){
            x_i = atoi(token2);
            token2 = strtok(NULL, " ") ;
            y_i = atoi(token2);
            token2 = strtok(NULL, " ") ;
            printf("%lld\n", rec(x_i, y_i, pairs, c));
        }
        free(dup2);
      }
    }

正如您所看到的，我所做的基本思路是构建一个dp表并相应地评估函数。提前感谢任何可以帮助我的人。

Answer 1

该函数可以非常快速地增长，因此溢出64位整数（您可以通过使用assert(rec(...) >= 0)来检查这一点（不保证但可能因溢出而失败））。使用自定义BigInteger实现或切换到Java / Python。

例如为n=20, a_i=1, b_i=0: f(x,y)=20*f(x-1,y)+c = O(20^x*(c+d))

大多数使用Java的统计数据也表明了这一点：https://open.kattis.com/problems/generalizedrecursivefunctions/statistics https://baylor.kattis.com/problems/generalizedrecursivefunctions/statistics