$$$\{ a \oplus b, a|b, a+b \}$$$ is an arithmetic sequence with common difference $$$a \& b$$$

Reasoning :

Consider

• problem $$$A$$$ with one boolean as input and arbitrary output
  
• problem $$$B$$$ with arbitrary input and one boolean as output
  

$$$A$$$ can never be an NP problem (only two possibilities $$$(0/1)$$$ and each have a fixed answer regardless of the output).
$$$B$$$ can be an NP problem (example : check whether array can be partitioned into two sets of equal sums)

Given a tree of $$$n$$$ nodes, I need to find for every directed edge $$$(a,b)$$$ in it the number of paths in the tree that start with this directed edge

This was a subproblem I faced in two recent contests (YAC3 B, Codecraft22 F)

I wrote a recursive DP solution to it in $$$O(2*edges)$$$ which is $$$O(2n-2)$$$, but it got TLE in both problems and so far I don't know why

Here is my code :

int n,ans=0,k;
vector<pair<int,int>>adj[INF],u;
vector<int>dp(SZ,-1);
int slv(int e)
{
 if(dp[e]!=-1){return dp[e];}
 int c=1,nd=u[e].second,pr=u[e].first;
 for(int i=0;i<adj[nd].size();i++)
 {
  int x=adj[nd][i].first;
  if(x==pr){continue;}
  c+=slv(adj[nd][i].second);
 }
 return dp[e]=c;
}

/// n --> size of the node
/// adj[i] --> the adjacency list, for node i it carries a vector of pairs for each edge of node i : (the index of an edge,  the node connected to node i by this edge)
/// dp[x] --> the answer for the required problem above for an edge of index x

I suspect this could be due to using recursion, is there a way to optimize calculating the answer for this subproblem? It has been haunting me for days :(

Here are my submissions if you are wondering how I got TLE:
YAC3 B
Codecraft22 F
I doubt it is in a subproblem other than this one

On DIV2s and EDUs, What rank should I get to make a CM performance? and how many problems should I solve to get that rank and how fast?
Because I have been struggling and keep getting ABC very fast, but still Expert performance, what should i do exactly??

We have an array $$$A$$$ of length $$$N$$$, let's define a function $$$f$$$ which takes 3 parameters $$$(L,R,K)$$$ such that $$$(1 ≤ L ≤ R ≤ N)$$$, $$$f(L,R,0)$$$ = $$$\displaystyle\sum\limits_{i=L}^R (A_i)$$$, and $$$f(L,R,K)$$$ = $$$\displaystyle\sum\limits_{i=L}^R (\sum\limits_{j=i}^R (f(i,j,K-1)))$$$

We are going to call the function $$$f$$$ $$$Q$$$ Times, What is the best time complexity you can achieve?

My best time complexity to solve this is using DP with 2D prefix sum to calculate the answer for every possible tuple (i,j,k) using previous tuples in O(n^2 * maxK), Unfortunately...That's not efficient

However, I have found an Extra Greedy+Math+Inclusion-Exclusion-Principle O(n) pre-processing and O(1) per query solution for $$$(K=0)$$$ or $$$(K=1)$$$, but that's all I could do

Any comments on this function?

Note : since the value of this function may grow rapidly beyond the 64-bit integer datatype limit, you are asked to calculate its value modulo $$$10^9+7$$$

If there is not such a number then i can create an algorithm for fast prime factorization that works with numbers up to $$$10^9$$$