Cerinta completa

There are variables and requirements. Requirements are represented as , meaning that the variable must be less than or equal to the variable.

Your task is to assign non-negative numbers smaller than to each variable and then calculate the number of different assignments satisfying all requirements. Two assignments are different if and only if at least one variable is assigned to a different number in both assignments. Print your answer modulo .

Input Format

The first line contains space-separated integers, and , respectively.
Each of the subsequent lines contains space-seperated integers describing the respective and values for an requirement.

Constraints

Output Format

Print your answer modulo .

Sample Input 0

6 7
1 3
0 1
2 4
0 4
2 5
3 4
0 2

Sample Output 0

1000

Explanation 0

There are variables and requirements.

Let the variables be in the array .

Requirements are –

One of the assignments is –

Similarly there are assignments possible.

Result = .

Limbajul de programare folosit: cpp14

Cod:

#include <stdio.h>
#include <stdlib.h>
#define INF 9999
#define MOD 1007
typedef struct _list{
  int mask;
  struct _list *next;
} list;
int table[13][13],dp1[13][13][14],dp3[9000][10];
list *dp2[9000];
int min(int x,int y);
int findleft(int mask,int n);
int getmask(int mask,int x,int n);

int main(){
  int n,m,x,y,i,j,k;
  list *t,*cur;
  for(i=0;i<13;i++)
    for(j=0;j<13;j++)
      table[i][j]=INF;
  scanf("%d%d",&n,&m);
  for(i=0;i<m;i++){
    scanf("%d%d",&x,&y);
    if(x!=y)
      table[x][y]=-1;
  }
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      dp1[i][j][0]=table[i][j];
  for(k=1;k<=n;k++)
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        dp1[i][j][k]=min(dp1[i][j][k-1],dp1[i][k-1][k-1]+dp1[k-1][j][k-1]);
  t=(list*)malloc(sizeof(list));
  t->mask=0;
  t->next=NULL;
  dp2[0]=t;
  for(i=1;i<(1<<n);i++){
    x=findleft(i,n);
    dp2[i]=dp2[i^(1<<x)];
    x=getmask(i,x,n);
    cur=dp2[i^x];
    while(cur){
      t=(list*)malloc(sizeof(list));
      t->mask=x|cur->mask;
      t->next=dp2[i];
      dp2[i]=t;
      cur=cur->next;
    }
  }
  for(i=0;i<(1<<n);i++)
    dp3[i][0]=1;
  for(i=1;i<10;i++)
    for(j=0;j<(1<<n);j++){
      dp3[j][i]=0;
      cur=dp2[j];
      while(cur){
        dp3[j][i]=(dp3[j][i]+dp3[cur->mask][i-1])%MOD;
        cur=cur->next;
      }
    }
  printf("%d",dp3[(1<<n)-1][9]);
  return 0;
}
int min(int x,int y){
  return (x>y)?y:x;
}
int findleft(int mask,int n){
  int i,j,flag;
  for(i=0;i<n;i++)
    if((1<<i)&mask){
      flag=0;
      for(j=0;j<n;j++)
        if(((1<<j)&mask) && i!=j)
          if(dp1[j][i][n]<0){
            flag=1;
            break;
          }
      if(!flag)
        return i;
    }
  for(i=-1;mask;i++,mask>>=1);
  return i;
}
int getmask(int mask,int x,int n){
  int ans=1<<x,i;
  for(i=0;i<n;i++)
    if(((1<<i)&mask) && dp1[x][i][n]<0)
      ans|=(1<<i);
  return ans;
}

Scor obtinut: 1.0

Submission ID: 464647647

Link challenge: https://www.hackerrank.com/challenges/requirement/problem

Requirement