CS Academy - Submission

C++1246 B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define PB push_back
#define MP make_pair
#define PII pair<int,int>
#define FIR first
#define SEC second
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
    x=0; char c=getchar(); int f=1;
    while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=310;
int mod;
inline void Add(int &x,int y) { x+=y; if(x>=mod) x-=mod; }
inline void Dec(int &x,int y) { x-=y; if(x<0) x+=mod; }
int Pow(int x,int y) { int res=1; for(;y;y>>=1,x=x*(ll)x%mod) if(y&1) res=res*(ll)x%mod; return res; }
int n;
int C[N][N],g[N],f[N],s[N][N];
int main() {
    rd(n),rd(mod);
    for(int i=0;i<=n;++i) for(int j=0;j<=i;++j) C[i][j]=j?(C[i-1][j]+C[i-1][j-1])%mod:1;
    for(int i=0;i<=n;++i) g[i]=Pow(2,i*(i+1)/2);
    s[0][0]=1;
    for(int i=0;i<n;++i)
        for(int j=0;j<=n;++j) if(s[i][j])
            for(int k=0;k+j<=n;++k)
                Add(s[i+1][j+k],s[i][j]*(ll)g[k]%mod);
    for(int i=0;i<=n;++i) {
        f[i]=g[i];
        for(int j=1;j*2<=i;++j)
            for(int k=0;k<=i-2*j;++k)
                Dec(f[i],f[i-2*j-k+j]*(ll)s[j][k]%mod*(ll)C[i-2*j-k+j][j]%mod);
    }
    printf("%d",f[n]);
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Summary

User: tequila_girl

Verdict: 100 points

Language: C++

CPU Time usage: 197 ms

Memory usage: 1248 KB

Source code: 1246 B

Compilation

Compilation done in 0.782 seconds.

Main.cpp: In function ‘void rd(T&)’:
Main.cpp:17:2: warning: this ‘while’ clause does not guard... [-Wmisleading-indentation]
   17 |  while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
      |  ^~~~~
Main.cpp:17:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘while’
   17 |  while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
      |                                              ^

Results

Test Number	CPU Usage	Memory Usage	Result
9	108 ms	1036 KB	OK
8	55 ms	1072 KB	OK
7	190 ms	1100 KB	OK
6	197 ms	1248 KB	OK
5	90 ms	1104 KB	OK
4	39 ms	972 KB	OK
3	20 ms	1088 KB	OK
2	16 ms	1008 KB	OK
1	16 ms	1080 KB	OK
0	15 ms	1084 KB	OK