Submission #229116

#	Time	Username	Problem	Language	Result	Execution time	Memory
229116		Salito	Zapina (COCI20_zapina)	C++14	0 / 110	5 ms	384 KiB

zapina

///https://oj.uz/problem/view/COCI20_zapina

#include<bits/stdc++.h>
using namespace std;
long long const mod = 1e9+7;
long long const one = 1;
long long const zero = 0;

long long dp[350][350][30];

long long F(long long n)
{
    int i;
    if(n==0)return zero;
    long long sum=1;
    for(i=2;i<=n;i++)
    {
        sum=(sum*i)%mod;
        //cout<<sum<<endl;
    }

    return sum%mod;
}

long long st(long long a, long long n)
{
    int i;
    if(n==0)return one;
    long long sum=a;
    for(i=1;i<n;i++)
        sum=(sum*a)%mod;

    return sum%mod;
}
void solve(int n)
{
    int i,j,k;

    dp[1][1][1] = n % mod;
    dp[1][2][1] = n*(n-1)/2%mod;
    //cout<<dp[1][1][1]<<endl;

    for(i=2;i<=n;i++)
    {
        dp[i][1][1]=dp[i-1][1][1];
        dp[i][2][1]=dp[i-1][2][1];
        //cout<<" "<<dp[i][1][1]<<endl;
        for(j=3;j<=n;j++)
        {
            if(j<i)dp[i][j][1]=dp[i-1][j][1];
            else
            for(k=1;k<=sqrt(2*n);k++)
            {
                //cout<<i<<" "<<j<<"   ";
                dp[i][j][k]=(dp[i-1][j][k] - dp[i-1][j-i][k-1] * (F(n-(j-i))/max(one,(F(i)*F(n-j)%mod))))%mod;

                //cout<<dp[i][j][k]<<endl;
            }
            //cout<<endl;
        }
    }

    long long ans=0;
    for(j=1;j<=n;j++)
        for(k=1;k<=sqrt(2*n);k++)
            ans=(ans+dp[n][j][k]*st(n-j,n-k))%mod;
    cout<<ans<<endl;
}
int main()
{
    int n;
    cin>>n;

    if(n==1)cout<<1<<endl;
    if(n==2)
        cout<<3<<endl;
    else solve(n);

	return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 33
• Subtask 3: 0 / 55