Hint:
we start from kk = 1, then kk += kk (2), kk += kk (4) but we cannot advance when kk > k.
get to the maximum kk with this and the remaining n - kk can be easily calculated with
(n - kk) / k + (((n - kk) % k) > 0)

my same logic got tle in c++ but AC in java so beware

Segment Tree/ Fenwick Tree with range update and point query

please give me some tips!

Edited by author 24.04.2022 16:19

k, n = [int(x) for x in input().split()]
a = list(map(int, input().split()))
m = 0

for i in a:
    m += i
    if (m - k >= 0):
        m -= k
    else:
        m = 0
print(m)

6 6
1 2
2 3
3 4
4 5
1 6
6 5
1 5 6
ans : 0

With e=0.0000001 I have WA#14

7 5
1 2 20
2 5 100
2 3 20
6 3 70
4 1 10
3 7 5

Answer: 220

Edited by author 21.04.2022 19:37

#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <vector>
#include <bitset>
#include <stack>
#include <sstream>
#include <algorithm>

#define ll long long
using namespace std;

#define maxn 1805
#define maxk 1805

const int MAX_ONE = 1000000000;

struct x86_64 {
    int Length = 0, BigNum[1024] = {};
    x86_64(int Num = 0) {
        int Index = 0;
        while (Num) {
            BigNum[Index++] = Num % MAX_ONE;
            Num /= MAX_ONE;
        }
        Length = Index;
    }
    void operator =(int Num) {
        memset(BigNum, 0, sizeof(BigNum));
        int Index = 0;
        while (Num) {
            BigNum[Index++] = Num % MAX_ONE;
            Num /= MAX_ONE;
        }
        Length = Index;
    }
};

void print(x86_64 Num) {
    for (int i = Num.Length - 1; i >= 0; i--) {
        if (i != Num.Length - 1) {
            printf("%09d", Num.BigNum[i]);
        } else {
            printf("%d", Num.BigNum[i]);
        }
    }
}

x86_64 operator +(x86_64 A, x86_64 B) {
    int Length = max(A.Length, B.Length);
    int Carry = 0;
    x86_64 Answer;
    for (int i = 0; i < Length + 1; i++) {
        Answer.BigNum[i] = (A.BigNum[i] + B.BigNum[i] + Carry) % MAX_ONE;
        Carry = (A.BigNum[i] + B.BigNum[i] + Carry) / MAX_ONE;
    }
    Answer.Length = (Answer.BigNum[Length] == 1) + Length;
    return Answer;
}

x86_64 operator *(x86_64 A, int B) {
    int Length = A.Length;
    int Carry = 0;
    x86_64 Answer;
    for (int i = 0; i < Length + 1; i++) {
        Answer.BigNum[i] = (A.BigNum[i] * (ll)B + Carry) % MAX_ONE;
        Carry = (A.BigNum[i] * (ll)B + Carry) / MAX_ONE;
    }
    int Index = 0;
    while (Answer.BigNum[Index] != 0) {
        Index++;
    }
    Answer.Length = Index;
    return Answer;
}

x86_64 dp[maxn][2];

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    dp[1][1] = K - 1;
    for (int i = 2; i <= N; i++) {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = dp[i - 1][0] + dp[i - 1][1] * (K - 1);
    }
    print(dp[N][0] + dp[N][1]);
    putchar('\n');
    return 0;
}

#include<iostream.h>
#include<stdio.h>
int main()
{
    int n,i,k;unsigned __int64 a[2000],p;
    cin>>n>>k;a[1]=k-1;a[2]=k*(k-1);
        for(i=3;i<=n;i++)
        {a[i]=(k-1)*(a[i-1]+a[i-2]);p=a[i];}
        if(n==1)
            cout<<k-1;
        else
            if(n==2)
                cout<<k*(k-1);
            else
                if(n>=3)
                    printf("%I64u", p);


    return 0;
}

Edited by author 10.04.2007 21:30

Edited by author 10.04.2007 21:31

Edited by author 10.04.2007 21:32

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    int mul = 1;
    string s;
    cin>>n>>s;
    int k = s.size();
    if(n%k==0){
        int in = n;
        int temp = k;
        while(1){
            mul = mul*in;
            in = in - k;
            if(in==k){
                mul*=in;
                break;
            }
        }
    }
    else{
        int in = n;
        while(1){
            mul = mul*in;
            in = in - k;
            if(in==(n%k)){
                mul*=in;
                break;
            }
        }
    }
    cout<<mul<<endl;
    return 0;
}

What is test case 2?

WA5,and never get Accept without High Eps.It isn't a good Problem.

what's the answer when N=170 and K=10?

If you get WA4, try this test:

2
3 1 3 2
1 5
NO

For WA5 try this:
2
1 5
1 5
YES

please,give 23 test

if you get runtime in c#, it's probably stack overflow. So use bfs instead of dfs, it helped me!

InPut
5 5
1 4
4 5
5 1
1 2
2 3

OutPut
3 2 1 4 5 1

Please show 8 test

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, s;
    cin >> n >> s;

    vector<int> nums(n + 1, 1);

    for (int i = s; i <= n; i++)
    {
        for (int j = 101; j <= 200; j++)
        {
            if ((i * j) % 100 == 0 and (i * j) / 100 <= n)
            {
                nums[(i * j) / 100] = nums[(i * j) / 100] > nums[i] + 1 ? nums[(i * j) / 100] : nums[i] + 1;
            }
        }
    }

    cout << nums[n] << endl;

    return 0;
}