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
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
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)