Specifically, although No should be output in the following cases, Yes is output in the case of the second code.

2
2 3
-1 -1

The reason this happened is that I didn't consider the number of pairs where $ (A \ _i, B \ _i) = (-1, -1) $ was stored in the variable ** $ ot $ . (See below for $ ot $). To take this into account, $ dp [l] [r] instead of $ dp [l] [r]: = $ (whether $ [l, r] $ consists of multiple intervals that satisfy the subject). Must be: = $ ( $ (A \ _i, B \ _i) = (-1, -1) $ minimum number of people in $ [l, r] $ **). And finally, if $ dp [0] [n-1] = ot $, Yes is output, otherwise No is output. In the above case, $ ot = 1 $ and $ dp [0] [n-1] = 2 $, which is not suitable.

Impressions

I couldn't think of it during the contest, but I was able to solve it by reviewing it. The implementation was heavy and WA was issued, but as a result, I was glad that I was able to solve it by myself. In addition, the following is not the policy when upsolving immediately after the contest, but the policy after understanding the section DP properly. The second part of the code is that. Furthermore, the interval DP is a DP ** that has the information of the interval $ [l, r] $ as ** $ dp [l] [r] $. For details, please refer to this article.

policy

First, in the first experiment, I thought that ** $ c \ _i $ could be divided into sections that were combined by equal people **. Also, given ** $ c \ _i $, that value uniquely determines the length of the interval ** (I didn't notice this during the contest). Therefore, conversely, when the interval $ [l, r] $ is given, the floors on which the people included in the interval ride and the floors on which they descend are uniquely determined as follows ($ (r-l + 1) \ % \ 2 = 0 $ is required). Also, in the figure below, $ k = \ frac {r-k + 1} {2} $ holds.

Also, when ** $ [l, r] $ is given, it seems that $ O (n) $ will show whether the interval is established as shown in the above figure **. Therefore, any $ l, r $ can indicate the establishment of this interval, and $ dp [l] [r]: = $ ($ [l, r] $ becomes one interval that satisfies the ** theme. You can prepare an array with whether or not **).

Furthermore, what we want to finally find is $ dp [l] [r]: = $ (whether $ [l, r] $ is composed of multiple intervals that satisfy the theme **), so * * It is necessary to merge each section ** to make a judgment.

From the above, you can write a program of $ O (n ^ 3) $, which is fast enough.

Implementation

Now that we have a basic policy, we will consider implementing it.

** (1) Preparation **

Receives the given person's information (boarding floor and descending floor) and saves it in the data structure. If you know both the floor to get on and the floor to get off, save the information in the array $ lr $ as "$ lr $ [floor to get on] = floor to get off". If only the floor to ride is known, the information is saved in the array $ lx $ as "$ lx $ [board] = True". If only the descending floor is known, save the information in the array $ rx $ as "$ rx $ [descending floor] = True". If you don't know which floor to get on or off, you'll want to use it for adjustments, so save that number in a variable called $ ot $.

Unless it is impossible in the first place when reading information as a preparation. In other words, ** when it becomes "boarding floor > descending floor" ** and ** when there are multiple same floors ** clearly do not satisfy the theme, so in this case, output No first and program I'm done.

** (2) Find $ dp [l] [r]: = $ (whether $ [l, r] $ is one interval that satisfies the theme) **

First, it is determined whether $ [l, r] $ is one interval for any $ l, r $. If ** $ (r-l) \% \ 2 = 0 $, it does not hold **, so look at the next section. Also, the difference between the floors where people descend and the floors included in this section is $ seglen = \ frac {r-l + 1} {2} $. Here, for any $ l \ leqq i \ leqq r-seglen $, it is judged in the following 6 cases whether $ i, i + seglen $ is appropriate as a set of the floor where the elevator rides and the floor where the elevator goes down.

[1] $ lr [i]! = -1 $ and $ lr [i]! = I + seglen $

** It is not suitable because you will get off on another floor **.

[2] When $ lx [i + seglen] $ is True or $ rx [i] $ is True

It is not suitable because the floor to get off and the floor to get on are opposite.

[3] When $ lr [i] = i + seglen $

The set of floors to get on and off is appropriate.

[4] When $ lx [i] $ is True and $ rx [i + seglen] $ is True

It is not suitable because $ i, i + seglen $ to be paired is ** on the floor where different people get on and on the floor where they get off **.

[5] When $ lx [i] $ is True or $ rx [i + seglen] $ is True

It is appropriate because you can properly decide which floor to get off or to get on.

[6] When $ lx [i] $ is False and $ rx [i + seglen] $ is False

It is appropriate because you can use the pair stored in $ ot $.

** (3) Find $ dp [l] [r]: = $ (whether $ [l, r] $ consists of multiple intervals that satisfy the theme) **

Merge the $ dp [l] [r] $ you just found and see if $ dp [0] [2n-1] $ is True.

At this time, if ** $ dp [l] [i] $ is True and $ dp [i + 1] [r] $ is True, then $ dp [l] [r] $ is True **, which is arbitrary. Try $ l, r, i $. You can merge correctly by turning the loop as $ l, r, i $ from the outside.

C.py

n=int(input())
#B against A
#It is slow to manage here with a dictionary
lr,lx,rx,ot=[-1]*(2*n),[0]*(2*n),[0]*(2*n),0
ab=[[j-1 for j in list(map(int,input().split()))] for i in range(n)]

check=[0]*(2*n)
for i in range(n):
    if ab[i][0]!=-2:
        check[ab[i][0]]+=1
    if ab[i][1]!=-2:
        check[ab[i][1]]+=1
    #If it is reversed
    if ab[i][0]!=-2 and ab[i][1]!=-2:
        if ab[i][0]>ab[i][1]:
            print("No")
            exit()

#When 2 or more are included
if any(i>1 for i in check):
    print("No")
    exit()

for i in range(n):
    if ab[i][0]==-2 and ab[i][1]==-2:
        ot+=1
    elif ab[i][0]==-2:
        rx[ab[i][1]]=1
    elif ab[i][1]==-2:
        lx[ab[i][0]]=1
    else:
        lr[ab[i][0]]=ab[i][1]

#dp[l][r]=([l,r]Minimum to use ot in)
#Will it be one position?
inf=10**12
dp=[[inf]*(2*n) for i in range(2*n)]
for l in range(2*n):
    #r is greater than l
    for r in range(l+1,2*n):
        dp_sub=0
        #Does this section certainly exist?(If it does not exist, change it to break immediately(Branch))
        seglen=(r-l+1)//2
        #The length of the section is odd(2x+1)
        #At that time, the section included in it is x+1 length
        if (r-l)%2==1:
            for i in range(l,r-seglen+1):
                #i and i+Seglen pair
                if lr[i]!=-1:
                    if lr[i]!=i+seglen:
                        break
                elif lx[i]:
                    if not rx[i+seglen]:
                        dp_sub+=0
                    else:
                        break
                elif rx[i]:
                    break
                else:
                    #i+Also the pattern where seglen is in rx
                    if not rx[i+seglen]:
                        #Only at this time(-1,-1)
                        dp_sub+=1
            #If this section meets the conditions
            else:
                dp[l][r]=dp_sub

#Find out if there are candidates in DFS from here
#Exit if even one is found
#If not, no
#Check if ot fits
def dfs(i,otc):
    if otc>ot:
        return
    if i==2*n:
        if otc==ot:
            print("Yes")
            exit()
        else:
            return
    for j in range(i+1,2*n):
        if dp[i][j]!=inf:
            dfs(j+1,otc+dp[i][j])
dfs(0,0)
print("No")

C2.py

n=int(input())
#B against A
#It is slow to manage here with a dictionary
lr,lx,rx,ot=[-1]*(2*n),[0]*(2*n),[0]*(2*n),0
ab=[[j-1 for j in list(map(int,input().split()))] for i in range(n)]

check=[0]*(2*n)
for i in range(n):
    if ab[i][0]!=-2:
        check[ab[i][0]]+=1
    if ab[i][1]!=-2:
        check[ab[i][1]]+=1
    #If it is reversed
    if ab[i][0]!=-2 and ab[i][1]!=-2:
        if ab[i][0]>ab[i][1]:
            print("No")
            exit()

#When 2 or more are included
if any(i>1 for i in check):
    print("No")
    exit()

for i in range(n):
    if ab[i][0]==-2 and ab[i][1]==-2:
        ot+=1
    elif ab[i][0]==-2:
        rx[ab[i][1]]=1
    elif ab[i][1]==-2:
        lx[ab[i][0]]=1
    else:
        lr[ab[i][0]]=ab[i][1]

#dp[l][r]=Will it be one position?
dp=[[False]*(2*n) for i in range(2*n)]
for l in range(2*n):
    #r is greater than l
    for r in range(l+1,2*n):
        #Does this section certainly exist?(If it does not exist, change it to break immediately(Branch))
        seglen=(r-l+1)//2
        #The length of the section is odd(2x+1)
        #At that time, the section included in it is x+1 length
        if (r-l)%2==1:
            for i in range(l,r-seglen+1):
                #Is lr different,l,Is it wrongly entered in r?
                if (lr[i]!=-1 and lr[i]!=i+seglen) or lx[i+seglen] or rx[i]:
                    #print(l,r,1)
                    break
                if lr[i]==i+seglen:
                    continue
                #Can it be included at the same time?
                if [lx[i],rx[i+seglen]].count(True)==2:
                    #print(l,r,2)
                    break
                elif [lx[i],rx[i+seglen]].count(True)==1:
                    continue
            #If this section meets the conditions
            else:
                dp[l][r]=True

#From here, it's OK if you merge the section DP and finally merge it
#dp[l][i],dp[i+1][r]True if both are True
for l in range(2*n):
    for r in range(l+1,2*n):
        for i in range(l+1,r):
            if dp[l][r]==False:
                if dp[l][i] and dp[i+1][r]:
                    dp[l][r]=True
                    break
#print(dp)
if dp[0][2*n-1]:
    print("Yes")
else:
    print("No")

D problem

I don't understand how to solve the correct answer, but I will explain it because I was able to pass it by increasing the speed by a constant multiple (✳︎1).

(The prime number for which you want to find the given remainder divided is shown below as $ mod $.)

Basic consideration

First of all, when the average is $ x $, it is typical that ** the whole amount is $ -x $ and the number of pieces is lost and the amount of calculation is reduced **. Therefore, consider the case where the sum of the following sequences is 0 when the average is $ x $.

At this time, consider the left side and the right side of 0 separately (✳︎2). Then, the left side is all negative and the right side is positive. Therefore, if both are aligned positively, ** the sum on the left and the sum on the right are equal **. Also, the left side is the sum when selecting from $ 1,2,…, x-1 $, and the right side is the sum when selecting from $ 1,2,…, nx $, so $ dp [i] [j]: If = $ (the number when the sum from 1 to $ i + 1 $ is $ j $) is calculated in advance, the final solution output is $ x = $ 1 ~ $ n $. It can be calculated by the amount of calculation of $ O (n ^ 3k) $ by comparing with $ j $.

DP part

Here, ** about the pre-calculated DP **, but since each number can be selected from 0 to $ k $ $ k + 1 $, there are $ k + 1 $ transitions. In other words, the amount of calculation is $ O (n ^ 3k ^ 2) $, and the maximum is $ n ^ 3k ^ 2 = 10 ^ {10} $. Here, in the answer, I dropped it to $ O (n ^ 3k) $ by the technique of the minimum slide value, but I passed it by increasing the speed by a constant times (✳︎1).

If you put the DP as before, the transition from $ dp [i-1] [j] $ will be as follows. Also, suppose you select only $ l $ for $ i + 1 $.

dp[i][j+l*(i+1)]+=dp[i-1][j]

Here, the answer should be output with the remainder of $ mod $, and at the same time I want to set $ dp [i] [j + l * (i + 1)] % = mod $, but ** $ % $ Since the operation takes time and only addition is done here **, you only need to subtract $ mod $ when $ dp [i] [j + l * (i + 1)] $ exceeds $ mod $. is.

Output part

By calculating DP, $ dp [i] [j] $ can be obtained for any $ i, j $, so consider the output.

First, when $ x = 1, n $, there are 1 to $ k $ $ k $ ways, and otherwise there are $ dp [n-2] [0] = 1 $ ways. , Multiply and divide by $ mod $ to find the remainder.

In other cases, when the value to be obtained as an answer is initialized as $ ans = 0 $ and only ** $ x $ is selected, ** is the same as $ k $, and other than ** $ x $ is also selected. ** is $ dp [x-2] [j] \ * dp [nx-1] [j] $ if the sum of left and right is equal to $ j $. For any $ j (\ geqq 1) $, add it to $ ans $ and finally find the remainder divided by $ mod $. Also, to avoid overflow **, take $ mod $ every time you multiply **. And since there are $ k + 1 $ ways to select $ x $, you can finally output $ ans \ * (k + 1) + k $.

(✳︎1)… I used "$% $ operation by $ mod $ for constant multiple speedup" and "** Do not see the sum ($ j $) that you do not need to see **".

(✳︎2)… ** It is easy to think that it will increase (or decrease) by 1 at the beginning **. I didn't think of a bug in my head during the contest ...

D.cc

//Debugging options:-fsanitize=undefined,address

//Compiler optimization
#pragma GCC optimize("Ofast")

//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair

signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,k,mod;cin>>n>>k>>mod;
    if(n==1){
        cout<<k<<endl;
        return 0;
    }else if(n==2){
        cout<<k<<endl;
        cout<<k<<endl;
        return 0;
    }
    ll ran=k*n*(n+1)/2;
    vector<vector<ll>> dp(n,vector<ll>(ran+1,0));
    REP(j,k+1){
        dp[0][j]=1;
    }
    FOR(i,1,n-1){
        REP(j,k*i*(i+1)/2+1){
            ll ran2=min(k+1,(ran-j)/(i+1)+1);
            REP(l,ran2){
                dp[i][j+l*(i+1)]+=dp[i-1][j];
                if(dp[i][j+l*(i+1)]>=mod)dp[i][j+l*(i+1)]-=mod;
            }
        }
    }
    cout<<k*dp[n-2][0]%mod<<endl;
    FOR(i,2,n-1){
        ll ans=0;
        FOR(j,1,ran){
            ans+=(dp[i-2][j]*dp[n-i-1][j]);
            ans%=mod;
        }
        cout<<((k+1)*ans+k)%mod<<endl;
    }
    cout<<k*dp[n-2][0]%mod<<endl;
}

After the E problem

I will not solve this time.