Submission #340088

#	Time	Username	Problem	Language	Result	Execution time	Memory
340088		Hazem	Zapina (COCI20_zapina)	C++14	110 / 110	865 ms	2540 KiB

zapina

/*
ID: tmhazem1
LANG: C++14
TASK: pprime
*/

#include <bits/stdc++.h>
using namespace std;

#define S second
#define F first
#define LL long long

const int N = 4e2 + 10;


LL LINF = 100000000000000000;
LL INF = 1000000000;
int MOD = 1e9+7;

int n;
int fac[N];
int dp[N][N][2],inverse[N];
int C1[N][N];

int mult(LL a,LL b){
    return (a*b)%MOD;
}

int fastpow(int n,int k){

    LL ret = 1;
    while(k){
        if(k&1)ret = mult(ret,n);
        k /= 2;
        n = mult(n,n);
    }
    return ret;
}

int add(LL a,LL b){
    return (a+b)%MOD;
}

int divide(LL a,LL b){
    return mult(a,fastpow(b,MOD-2));
}

int C(LL n,LL k){

    return divide(fac[n],mult(fac[k],fac[n-k]));
}

int solve(int i,int j,bool q){

    if(i==n+1)
        return j==n&&q;

    if(dp[i][j][q]!=-1)
        return dp[i][j][q];

    LL ret = 0;
    for(int k=0;k<=n-j;k++)
        ret = add(ret,mult(C1[n-j][k],solve(i+1,j+k,q|(k==i))));

    return dp[i][j][q] = ret;
}

int main()
{
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    memset(dp,-1,sizeof(dp));

    fac[0] = 1;
    for(int i=1;i<=n;i++)
        fac[i] = mult(fac[i-1],i);

    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
        C1[i][j] = C(i,j);

    printf("%d\n",solve(1,0,0));
}       

Compilation message (stderr)

zapina.cpp: In function 'int main()':
zapina.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~

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