| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 498648 |
2021-12-26T04:43:06 Z |
model_code |
NoM (RMI21_nom) |
C++17 |
|
78 ms |
328 KB |
// nom_100_panaete.cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int N = 2005;
int n,d,L,R,X,newL,newR,puse,ramase,K,F[N],I[N],comb(int,int),cat,rest,A[N],B[N],*a,*b;
inline int suma(int a,int b)
{
a=(a+b)%MOD;
return a;
}
inline int prod(int a,int b)
{
a=1LL*a*b%MOD;
return a;
}
inline int comb(int n,int k)
{
return prod(F[n],prod(I[k],I[n-k]));
}
void init(),procesare();
int main()
{
init();
while(ramase)
{
K=cat;
if(rest)
{
K++;
rest--;
}
newL=3*n;
newR=-1;
for(X=L; X<=R; X++)procesare();
L=newL;
R=newR;
puse+=K;
ramase-=K;
swap(a,b);
}
int Sol=a[n];
for(int i=1; i<=n; i++)Sol=prod(2,Sol);
cout<<Sol<<'\n';
return 0;
}
void init()
{
a=A;
a[0]=1;
b=B;
cin>>n>>d;
cat=2*n/d; /// dimensiunea standard a unei grupe
rest=2*n%d; /// numarul de grupe mai mari cu 1 fata de dimensiunea standard
ramase=2*n; /// numarul de valori pe care le mai am de pus
F[0]=1; /// initializare calcul factoriale
for(int i=1; i<=2000; i++)F[i]=prod(i,F[i-1]); /// calcul factoriale
int x=F[2000],e=MOD-2,r=1;
for(; e; e>>=1,x=prod(x,x))r=(e&1)?prod(r,x):r; /// calcul (2000!)^(-1)
I[2000]=r; /// initializare calcul inverse factoriale
for(int i=2000; i>=1; i--)I[i-1]=prod(i,I[i]); /// calcul inverse factoriale [(i-1)!]^(-1) = i * (i!)^(-1)
}
void procesare()
{
/// se completeaza o noua grupa de dimensiune K
/// puse = numarul de valori deja folosite in grupele anterioare
/// U2 = X = numarul de valori folosite de doua ori[tip 2]
/// U1 = Y = numarul de valori folosite o data[tip 1]
/// U0 = Z = numarul de valori nefolosite inca[tip 0]
int Y=puse-2*X,Z=n-X-Y;
int maxY=min(Y,K),maxZ=min(Z,K);
int minY=K-maxZ;
newL=min(newL,X+minY);
newR=max(newR,X+maxY);
for(int UY=minY,UZ=K-minY; UY<=maxY; UY++,UZ--)
b[X+UY]=suma(b[X+UY],prod(F[K],prod(a[X],prod(comb(Y,UY),comb(Z,UZ)))));
a[X]=0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
224 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
224 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
208 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
224 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
208 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
2 ms |
208 KB |
Output is correct |
| 23 |
Correct |
1 ms |
208 KB |
Output is correct |
| 24 |
Correct |
2 ms |
204 KB |
Output is correct |
| 25 |
Correct |
3 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
252 KB |
Output is correct |
| 27 |
Correct |
2 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
224 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
208 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
2 ms |
208 KB |
Output is correct |
| 23 |
Correct |
1 ms |
208 KB |
Output is correct |
| 24 |
Correct |
2 ms |
204 KB |
Output is correct |
| 25 |
Correct |
3 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
252 KB |
Output is correct |
| 27 |
Correct |
2 ms |
204 KB |
Output is correct |
| 28 |
Correct |
4 ms |
312 KB |
Output is correct |
| 29 |
Correct |
7 ms |
204 KB |
Output is correct |
| 30 |
Correct |
8 ms |
312 KB |
Output is correct |
| 31 |
Correct |
3 ms |
208 KB |
Output is correct |
| 32 |
Correct |
9 ms |
328 KB |
Output is correct |
| 33 |
Correct |
10 ms |
316 KB |
Output is correct |
| 34 |
Correct |
16 ms |
316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
224 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
1 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
1 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
204 KB |
Output is correct |
| 15 |
Correct |
1 ms |
204 KB |
Output is correct |
| 16 |
Correct |
1 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
208 KB |
Output is correct |
| 19 |
Correct |
1 ms |
204 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
204 KB |
Output is correct |
| 22 |
Correct |
2 ms |
208 KB |
Output is correct |
| 23 |
Correct |
1 ms |
208 KB |
Output is correct |
| 24 |
Correct |
2 ms |
204 KB |
Output is correct |
| 25 |
Correct |
3 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
252 KB |
Output is correct |
| 27 |
Correct |
2 ms |
204 KB |
Output is correct |
| 28 |
Correct |
4 ms |
312 KB |
Output is correct |
| 29 |
Correct |
7 ms |
204 KB |
Output is correct |
| 30 |
Correct |
8 ms |
312 KB |
Output is correct |
| 31 |
Correct |
3 ms |
208 KB |
Output is correct |
| 32 |
Correct |
9 ms |
328 KB |
Output is correct |
| 33 |
Correct |
10 ms |
316 KB |
Output is correct |
| 34 |
Correct |
16 ms |
316 KB |
Output is correct |
| 35 |
Correct |
25 ms |
316 KB |
Output is correct |
| 36 |
Correct |
59 ms |
320 KB |
Output is correct |
| 37 |
Correct |
20 ms |
216 KB |
Output is correct |
| 38 |
Correct |
39 ms |
320 KB |
Output is correct |
| 39 |
Correct |
48 ms |
204 KB |
Output is correct |
| 40 |
Correct |
78 ms |
312 KB |
Output is correct |
