How to calculate number of ordered solutions to x+y+z = u+v+w, 0 <= x, y, z, u, v, w < n.
Difference between en1 and en2, changed 18 character(s)
So I'm trying to solve this problem but my solution has O(n^6) complexity and I don't know how you can do this faster.↵
↵
~~~~~↵
int ans = 0;↵
for(int i = 0; i < n; i++){↵
    for(int j = 0; j < n; j++){↵
        for(int k = 0; k < n; k++){↵
            for(int x = 0; x < n; x++){↵
                for(int y = 0; y < n; y++){↵
                     for(int z = 0; z < n; z++){↵
                         if(i + j + k == x + y + z) ans++;↵
                     }↵
                 }↵
            }↵
        }↵
    }↵
}↵
cout << ans << "\n";↵
~~~~~↵
↵
I looked up the sequence on OEIS but there isn't any other relevant information.            ↵
https://oeis.org/search?q=1+%2C+20+%2C+141+%2C+580+%2C+1751&language=english&go=Search           ↵
I need to calculate this fast for n <= 100000.        ↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English PoIycarp 2024-03-31 23:07:10 18
en1 English PoIycarp 2024-03-31 23:06:28 889 Initial revision (published)