I have the following problem

Given an array of n integers called a (n <= 10^3 and |a[i]| <= 10^4). Given an integer M, count the number of increasing subsequenes such that the sum of their elements equal to M.

E.g: with the input

6 11

7 1 4 3 5 6

The results should be 2 since 2 subsequences (1,4,6) and (5,6) satisfy the conditions.

I have approached an algorithm that results in O(n^2*m) complexity. But still, I'm wondering is there an even better way to optimize this algorithm? Hopefully you guys can help me

Hey there,

I just took a programming contest and received a pretty interesting mathematical problem.

To sum up, you are given two numbers n and k (1 <= n <= 10^18, 1 <= k <= 10^6).

Assume that F(i) is the i-th number in the Fibonacci sequence

E.g: F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, e.t.c.

Calculate the sum S of the first n Fibonacci numbers raised to the power of k.

Or in terms of pseudocode:

S = 0
for (i = 1 -> n)
    S = S + F(i)^k

Print the answer modulo 998244353. Is there any good approach to this problem? Thank you for reading!

Here's the link to the problem

https://cses.fi/problemset/task/1712

And here's my first approach to the problem

#include <bits/stdc++.h>
#define ll unsigned long long
#define nl '\n'
using namespace std;
const ll vpn=1e5+7;
const ll mod=1e9+7;
ll m,n,k,t;
ll a[vpn];
bool iscrit[vpn];
vector<ll> adj[vpn];
ll power(ll a,ll b,ll m)
{
    ll r=1;
    while (b)
    {
        if (b&1)
            r=r*a%m;
        a=a*a%m;
        b/=2;
    }
    return r;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("C://Users/Admin/Desktop/input.txt","r",stdin);
    freopen("C://Users/Admin/Desktop/output.txt","w",stdout);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>m>>n>>k;
        cout<<power(m,power(n,k,mod),mod)<<nl;
    }
}

But I've got all wrong answer, turns out when processing the power(n,k,mod) , it had to be power(n,k,mod-1) . Can someone explain me why do we have to power it and modulo by mod-1?

I'm having a trouble with problem 1B — Spreadsheet, the problem is here

1B - Электронные таблицы

This is my submission for the problem

122567113

I'm not sure what makes the 860th line in the 6th test returns that output. Can you guys help me figure it out what's the problem please, thanks