SCORESUM7 - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: satyam_343
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

The score of an array B of length M is defined to be

\sum_{i=1}^{M-1} (-1)^{i+1}|B_i - B_{i+1}|^7

Given an array A, find the sum of scores of all its subsequences.

EXPLANATION:

The score of an array is determined only by its adjacent elements.
So, instead of fixing a subsequence of A and finding its score, let’s fix a pair of adjacent elements in the subsequence, and count the contribution of this pair to the total score sum.

So, fix indices 1 \leq i \lt j \leq N, and let’s say indices i and j are to be adjacent in the subsequence.
This means we’re free to choose (or not choose) any indices before i and after j, but anything between them definitely cannot be chosen since they’ll stop being adjacent.
In total, this pair is therefore adjacent in 2^{i-1}\cdot 2^{N-j} subsequences.

Of them, by definition of the score, it contributes |A_i - A_j|^7 whenever the subsequence contains an even number of elements before i, and -(|A_i - A_j|^7) whenever there’s an odd number of elements before i.

However, if i\gt 1, the number of subsequences with an even number of elements before i equals the number of subsequences with an odd number of elements before i.

Why?

If i\gt 1, then any even-length subsequence containing 1 can be converted into an odd-length one by removing 1, and vice versa.
This gives us a bijection between even-length and odd-length subsequences, so of course their number is equal.

For a more algebraic proof, note that if we choose the elements of the subsequence that are \gt 1, then there’s a unique choice for 1 (either it must be included in the subseqeuence, or it mustn’t) to obtain an even-length subsequence.
This means there are exactly 2^{i-2} even-length subsequences, which is half of 2^{i-1} (so the odd-length subsequences form the other half).

This means, if i \gt 1, for any j we add |A_i - A_j|^7 and -(|A_i - A_j|)^7 to the sum an equal number of times — so they just cancel out!
So, it suffices to consider only i = 1.
But this is easy: since i = 1 there are always 0 elements (an even number) before it, and as noted earlier for any j\gt i there are 2^{i-1}\cdot 2^{N-j} = 2^{N-j} subsequences where this pair is adjacent.
So, |A_1 - A_j|^7 contributes to the total sum exactly 2^{N-j} times.

The final answer is thus just

\sum_{j=2}^N |A_1 - A_j|^7\cdot 2^{N-j}

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++)
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>   
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;   
using namespace std;
#define ll long long
#define pb push_back                  
#define mp make_pair          
#define nline "\n"                            
#define f first                                            
#define s second                                             
#define pll pair<ll,ll> 
#define all(x) x.begin(),x.end()     
#define vl vector<ll>           
#define vvl vector<vector<ll>>      
#define vvvl vector<vector<vector<ll>>>          
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif     
void _print(ll x){cerr<<x;}  
void _print(char x){cerr<<x;}   
void _print(string x){cerr<<x;}    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());   
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";} 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
const ll MOD=998244353;
const ll MAX=2000200;
vector<ll> fact(MAX+2,1),inv_fact(MAX+2,1);
ll binpow(ll a,ll b,ll MOD){
    ll ans=1;
    a%=MOD;  
    while(b){
        if(b&1)
            ans=(ans*a)%MOD;
        b/=2;
        a=(a*a)%MOD;
    }
    return ans;
}
ll inverse(ll a,ll MOD){
    return binpow(a,MOD-2,MOD);
} 
void precompute(ll MOD){
    for(ll i=2;i<MAX;i++){
        fact[i]=(fact[i-1]*i)%MOD;
    }
    inv_fact[MAX-1]=inverse(fact[MAX-1],MOD);
    for(ll i=MAX-2;i>=0;i--){
        inv_fact[i]=(inv_fact[i+1]*(i+1))%MOD;
    }
}
ll nCr(ll a,ll b,ll MOD){
    if(a==b){
        return 1;
    }
    if((a<0)||(a<b)||(b<0))
        return 0;   
    ll denom=(inv_fact[b]*inv_fact[a-b])%MOD;
    return (denom*fact[a])%MOD;  
} 
ll sum=0;
void solve(){  
    ll n; cin>>n;
    vector<ll> a(n+5);
    ll ans=0;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        ans=(ans+binpow(abs(a[i]-a[1]),7,MOD)*binpow(2,n-i,MOD))%MOD;
    }
    cout<<ans<<nline;
    return;    
}                                       
int main()                                                                               
{       
    ios_base::sync_with_stdio(false);                          
    cin.tie(NULL);                               
    #ifndef ONLINE_JUDGE                 
    freopen("input.txt", "r", stdin);                                           
    freopen("output.txt", "w", stdout);      
    freopen("error.txt", "w", stderr);                        
    #endif     
    ll test_cases=1;                   
    cin>>test_cases;
    precompute(MOD);
    while(test_cases--){
        solve();
    }
    debug(sum);
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}  
Editorialist's code (Python)
mod = 998244353
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans, pw = 0, 1
    for i in reversed(range(1, n)):
        ans += pow(abs(a[i] - a[0]), 7, mod))*pw
        pw = (pw * 2) % mod
    print(ans % mod)
for _ in range(int(input())):
    n=int(input())
    arr=list(map(int,input().split()))
    s=0
    
    for i in range(1,n):
        s+= pow(abs(arr[0]-arr[i]),7)* pow(2,(n-1-i))
    print(s%998244353)

Can any Python user tell me the reason for TLE?