c++ - 在 IARCS 中解决 NUMROUTE

Question

问题的链接是 ( Docs )虽然我使用下面的代码解决了它，但它给出了 SEG错误为len<=10^9我的程序可能用完了堆栈内存。我该如何优化它？或者有更好的解决方案吗？

#include <iostream>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <list>
using namespace std;
#define pb push_back

struct nd
{
    int val;int times;  
};
vector<list<nd> > adj_list;
int end;
int recur(int node, int len)
{ list<nd> ::iterator it;
    if(len==1)
    {//cout<<"reaching "<<node<<endl;
        int y=0;
        for(it=adj_list[node].begin(); it!=adj_list[node].end(); it++)
        {
            if((it->val)==end){y=it->times+y;}

        }
        return y;

    }
    else {
        int sum=0;
            //cout<<"going "<<node<<" length "<<len<<endl;
        for(it=adj_list[node].begin(); it!=adj_list[node].end(); it++)
        {

        sum+=it->times*recur(it->val,len-1);
        }
        return sum;
    }
}
int main()
{

    int n;
    cin>>n;
    adj_list.resize(n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int a;cin>>a;
            nd temp;
            temp.val=j;temp.times=a;
            adj_list[i].pb(temp);
        }
    }
    int st,len;
    cin>>st>>end>>len;
    st--;end--;
    list<nd> ::iterator it;
    int ans=0;
    for(it=adj_list[st].begin(); it!=adj_list[st].end(); it++)
    {
        int p=it->times*recur(it->val,len-1);
            //cout<<*it<<" "<<p<<endl;
        ans+=p;
    }
    cout<<ans%42373<<endl;
}

Answer 1

为 multimap 创建一个邻接矩阵A，并取它的k次方。结果矩阵的第 i,j 项是从节点 i 到节点 j 的步行次数。

示例:我们有两个节点，0 和 1，它们之间有两个连接，a 和 b.

   0
  / \
 a   b
  \ /
   1

邻接矩阵是

0 2
2 0

它的二次方是

4 0 
0 4

实际上，从节点 0 到节点 0 有四条长度为 2 的路径:aa, ab, ba, bb。

Here're a few notes on this .

顺便说一句，您可以使用 binary exponentiation 快速计算大幂次.