Submission #1289701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289701		orzngaiha	Tents (JOI18_tents)	C++20	100 / 100	1143 ms	83168 KiB

tents

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
const int MOD = 1e9+7;
long long n,p[N],k,m,dp[N][N];
long long modulo(long long a,long long b)
{
    long long r = 1;
    while(b)
    {
        if(b%2)
            r = (r*a)%MOD;
        a  = (a*a)%MOD;
        b = b/2;
    }
    return r;
}
long long cc(int n,int k)
{
    if(n < 0)
        return 0;
   long long x = p[n];
   long long y = (p[n-k]*p[k])%MOD;
   return (x*modulo(y,MOD-2))%MOD;
}
int main()
{
   cin>>n>>m;
     p[0] = 1;
   for(int i = 1;i <= max(n,m);i++)
      p[i] = (p[i-1]*i)%MOD;
   long long t = cc(m,2),ans = 0;
   dp[0][0] = 1;
   for(int i = 1;i <= n;i++)
   {
     for(int j = 0;j <= m;j++)
     {
        dp[i][j] = (dp[i][j] + dp[i-1][j])%MOD;
        dp[i][j+1] =  (dp[i][j+1] + (dp[i-1][j]*(m-j)*4)%MOD)%MOD;
        dp[i][j+1] =  (dp[i][j+1] + (dp[i-2][j]*(m-j)*(i-1))%MOD)%MOD;
        long long t = cc(m-j,2);
        if(j+2 <= m)
        dp[i][j+2] = (dp[i][j+2] +  (dp[i-1][j]*t)%MOD)%MOD;
     }
   }
    for(int i = 1;i <= m;i++)
    {
       ans = (ans + dp[n][i])%MOD;
    }
   cout<<ans;




}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52