[DP] Codeforces 840C .On the Bench

5437 단어 DP

%%%Vectorxj

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N=610,P=1e9+7;

int n,x,f[2][N];
map<int,int> mp;
vector<int> a;

int fac[N],inv[N];

inline int C(int x,int y){
    return 1LL*fac[x]*inv[y]%P*inv[x-y]%P;
}

inline void add(int &x,int y){
    if((x+=y)>=P) x-=P;
}

int main(){
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    scanf("%d",&n);

    fac[0]=inv[0]=inv[1]=1;
    for(int i=1;i<=600;i++) fac[i]=1LL*i*fac[i-1]%P;
    for(int i=2;i<=600;i++) inv[i]=1LL*(P-P/i)*inv[P%i]%P;
    for(int i=1;i<=600;i++) inv[i]=1LL*inv[i]*inv[i-1]%P;

    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        for(int j=2;j*j<=x;j++)
            while(x%(j*j)==0) x/=j*j;
        mp[x]++;
    }
    for(auto i : mp) a.push_back(i.second);
    int s=0,tot=a[0]; f[s][a[0]-1]=1;
    for(int g=1;g1){
        int nxt=a[g];
        for(int i=0;i<=n;i++) f[s^1][i]=0;
        for(int i=0;ifor(int j=1;j<=nxt;j++)
                for(int k=0;k<=j && k<=i;k++)
                    if(tot-i+1>=j-k)
                        add(f[s^1][i-k+nxt-j],1LL*f[s][i]*C(i,k)%P*C(tot-i+1,j-k)%P*C(nxt-1,j-1)%P);
        tot+=nxt;
    }
    for(int i : a) f[s][0]=1LL*f[s][0]*fac[i]%P;
    printf("%d
",f[s][0]);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다