Diagonal Sum of Powers
Autumn Tournament (2010)
Submission name: power.cpp
Problem summary
The first row has n bases. Column i contains successive powers of its base. Sum the diagonal beginning in row 2, column 1: a1²+a2³+…+an^(n+1), modulo m.
Input
n and m, then n positive integer bases.
Output
The diagonal sum modulo m.
Constraints
1 ≤ n ≤ 1000000; 1 ≤ m ≤ 10000000; 1 ≤ ai < 100000.
Worked example
Original statement sample.
Input
4 3 3 5 2 1
Output
1
Solution analysis
- The diagonal does not start in the first row. With 1-based columns, column i contributes exponent i+1. Read one base at a time; the full table never needs to be built.
- Use binary exponentiation: repeatedly square the current power and multiply it into the result only when the current exponent bit is one. Reduce every multiplication modulo m. This evaluates an exponent in O(log exponent), rather than performing exponent individual multiplications.
- In the sample the diagonal is 3²+5³+2⁴+1⁵=9+125+16+1=151. Its remainder modulo 3 is 1. Accumulate the modular residues; the residue of a sum equals the sum of residues modulo m.
Why it works
Binary exponentiation preserves result·base^remainingExponent modulo m when processing each bit, so it returns each requested power residue. The diagonal index identifies exactly one power from each column. Modular addition then yields the remainder of their sum.
Watch out. The first exponent is 2, not 1. Floating-point pow loses accuracy and must not be used. Multiplying residues can reach nearly 10^14, so use long long. For m=1, every residue is zero.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
using namespace std;
long long modularPower(long long base,int exponent,long long modulus){
long long result=1%modulus;
base%=modulus;
while(exponent>0){
if(exponent%2==1){
result=result*base%modulus;
}
base=base*base%modulus;
exponent/=2;
}
return result;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long modulus;
cin>>n>>modulus;
long long answer=0;
for(int column=1;column<=n;column++){
long long base;
cin>>base;
// The diagonal begins on the second row.
answer=(answer+modularPower(base,column+1,modulus))%modulus;
}
cout<<answer<<'\n';
}