| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 646015 |
2022-09-28T13:47:59 Z |
Kripton |
NoM (RMI21_nom) |
C++14 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int lgput(int a,int b)
{
int rez=1;
while(b)
{
if(b%2)
rez=1LL*rez*a%MOD;
a=1LL*a*a%MOD;
b/=2;
}
return rez;
}
template <const int MOD> struct numar{
int x;
numar(int x=0){
this->x=x;
}
bool operator!=(const numar &other) const{
return x!=other.x;
}
numar& operator=(const numar &other){
x=other.x;
}
numar operator+(const numar &other) const{
return numar(x+other.x>=MOD?x+other.x-MOD:x+other.x);
}
numar operator-(const numar &other) const{
return numar(x-other.x<0?x-other.x+MOD:x-other.x);
}
numar operator*(const numar &other) const{
return numar(1LL*x*other.x%MOD);
}
numar operator/(const numar &other) const{
return numar(1LL*x*lgput(other.x,MOD-2)%MOD);
}
void afis()
{
cout<<x;
}
};
numar <MOD> fact[4001],invfact[4001];
numar <MOD> dp[2][2001];
int exist[2],exidr[2];
numar <MOD> comb(int a,int b)
{
if(b>a)
return 0;
return fact[a]*invfact[b]*invfact[a-b];
}
int main()
{
int n,m,i,j,l;
cin>>n>>m;
fact[0]=1;
for(i=1;i<=2*n;i++)
fact[i]=fact[i-1]*i;
invfact[2*n]=lgput(fact[2*n].x,MOD-2);
for(i=2*n-1;i>=0;i--)
invfact[i]=invfact[i+1]*(i+1);
int cnt2=2*n%m;//2*n/m+1
int cnt1=m-cnt2;//2*n/m;
int k=2*n/m;
int sum=k;
dp[1][n-k]=comb(n,k)*fact[k];
exist[1]=n-k;
exidr[1]=n-k;
for(i=1;i<=cnt1-1;i++)
{
for(j=0;j<=n;j++)
dp[1-(i&1)][j]=0;
exist[1-(i&1)]=n+1;
exidr[1-(i&1)]=-1;
for(j=exist[i&1];j<=exidr[i&1];j++)
if(dp[i&1][j]!=0)
{
int unu=(n-j)*2-sum;
if(unu>=0)
for(l=max(j-k,0);l<=j;l++)
{
if(k-(j-l)>unu)
break;
dp[1-(i&1)][l]=dp[1-(i&1)][l]+dp[i&1][j]*fact[k]*comb(j,j-l)*comb(unu,k-(j-l));
exist[1-(i&1)]=min(exist[1-(i&1)],l);
exidr[1-(i&1)]=max(exidr[1-(i&1)],l);
}
}
sum+=k;
}
k++;
for(;i<=cnt1+cnt2-1;i++)
{
for(j=0;j<=n;j++)
dp[1-(i&1)][j]=0;
exist[1-(i&1)]=n+1;
exidr[1-(i&1)]=-1;
for(j=exist[i&1];j<=exidr[i&1];j++)
if(dp[i&1][j]!=0)
{
int unu=(n-j)*2-sum;
if(unu>=0)
for(l=max(j-k,0);l<=j;l++)
{
if(k-(j-l)>unu)
break;
dp[1-(i&1)][l]=dp[1-(i&1)][l]+dp[i&1][j]*fact[k]*comb(j,j-l)*comb(unu,k-(j-l));
exist[1-(i&1)]=min(exist[1-(i&1)],l);
exidr[1-(i&1)]=max(exidr[1-(i&1)],l);
}
}
sum+=k;
}
dp[m%2][0].afis();
return 0;
}
Compilation message
Main.cpp: In instantiation of 'numar<MOD>& numar<MOD>::operator=(const numar<MOD>&) [with int MOD = 1000000007]':
Main.cpp:57:13: required from here
Main.cpp:26:5: warning: no return statement in function returning non-void [-Wreturn-type]
25 | x=other.x;
+++ |+ return *this;
26 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
