Codeforces Round #277.5 (Div. 2)部分题解 - c++编程基础

n"t make the rhombus any more appealing to Tomash, so the four intersections remain a "damn rhombus" for him.

Given that the capital of Berland has n intersections and m roads and all roads are unidirectional and are known in advance, find the number of "damn rhombi" in the city.

When rhombi are compared, the order of intersections b and d doesn't matter.

Input

The first line of the input contains a pair of integers n, m (1 ≤ n ≤ 3000, 0 ≤ m ≤ 30000) ― the number of intersections and roads, respectively. Next m lines list the roads, one per line. Each of the roads is given by a pair of integers ai, bi (1 ≤ ai, bi ≤ n;ai ≠ bi) ― the number of the intersection it goes out from and the number of the intersection it leads to. Between a pair of intersections there is at most one road in each of the two directions.

It is not guaranteed that you can get from any intersection to any other one.

Output

Print the required number of "damn rhombi".

Sample test(s) input

output

input

output

暴力就好，如果u，v之间长度为2的路径有x条，且x>1,那么显然以u，v为起点和终点的四边形有c(x,2)个

/*************************************************************************
    > File Name: cf.cpp
    > Author: acvcla
    > QQ:
    > Mail: acvcla@gmail.com 
    > Created Time: 2014年11月17日 星期一 23时34分13秒
 ************************************************************************/
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 using namespace std; typedef long long LL; const int maxn = 3e3 + 10; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back int n,m; std::vector
                
                  G[maxn]; int d[maxn][maxn]; void dfs(int u,int v,int dist){ if(dist>2)return; if(dist==2){ ++d[u][v];return ; } for(int i=0;i
                 
                  >n>>m){ for(int i=1;i<=n;i++)G[i].clear(); memset(d,0,sizeof d); int u,v; for(int i=1;i<=m;i++){ cin>>u>>v; G[u].pb(v); } LL ans=0; for(int i=1;i<=n;i++)dfs(i,i,0); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(d[i][j]<2||j==i)continue; //cout<

F. Special Matrices time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

An n × n square matrix is special, if:

it is binary, that is, each cell contains either a 0, or a 1;
the number of ones in each row and column equals 2.
You are given n and the first m rows of the matrix. Print the number of special n × n matrices, such that the first m rows coincide with the given ones.

As the required value can be rather large, print the remainder after dividing the value by the given numbermod.
Input
The first line of the input contains three integers n, m, mod (2 ≤ n ≤ 500, 0 ≤ m ≤ n, 2 ≤ mod ≤ 109). Thenm lines follow, each of them contains n characters ― the first rows of the required special matrices. Each of these lines contains exactly two characters '1', the rest characters are '0'. Each column of the given m × ntable contains at most two numbers one.
Output
Print the remainder after dividing the required value by number mod.
Sample test(s) input
```
3 1 1000
011
```
output
```
2
```
input
```
4 4 100500
0110
1010
0101
1001
```
output
```
1
```
Note
For the first test the required matrices are:
```
011
101
110

011
110
101
```
In the second test the required matrix is already fully given, so the answer is 1.

按行dp，由于每行的和必须为2，所以可以在新建行的时候在列和为1或0的位置上选出两个来添加。直到最终列和全部为2.

具体看代码
```
/*************************************************************************
    > File Name: cf.cpp
    > Author: acvcla
    > QQ: 
    > Mail: acvcla@gmail.com 
    > Created Time: 2014年11月17日 星期一 23时34分13秒
 ************************************************************************/
#include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #inclu
            
```

Codeforces Round #277.5 (Div. 2)部分题解(三)