제출 #1334986

#제출 시각아이디문제언어결과실행 시간메모리
1334986tudor_costinPet (COCI26_pet)C++20
35 / 110
23 ms19552 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Nmax=2005,mod=1e9+7;
int dp[Nmax][Nmax][5][3];
int s[Nmax][3];
bitset<Nmax> b[Nmax];
int lin=0,col=1;
///lin->0
///col->0
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        string str;
        cin>>str;
        for(int j=1;j<=m;j++)
        {
            if(str[j-1]=='1')
            {
                dp[i][j][1][0]=1;
                dp[i][j][1][1]=1;
                s[i][col]++;
                s[j][lin]++;
                b[i][j]=1;
            }
            else b[i][j]=0;
        }
    }
    int ans=0;
    for(int k=2;k<=5;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(b[i][j])
                {
                    dp[i][j][k][lin]=(s[i][col]+mod-dp[i][j][k-1][col])%mod;
                    dp[i][j][k][col]=(s[j][lin]+mod-dp[i][j][k-1][lin])%mod;
                    if(k==5)
                    {
                        ans=(ans+dp[i][j][k][lin]+dp[i][j][k][col])%mod;
                    }
                   /// cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k][lin]<<' '<<dp[i][j][k][col]<<'\n';
                }
            }
        }
        if(k==5) break;
        for(int i=1;i<=n;i++) s[i][col]=0;
        for(int i=1;i<=m;i++) s[i][lin]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                s[i][col]=(s[i][col]+dp[i][j][k][col])%mod;
                s[j][lin]=(s[j][lin]+dp[i][j][k][lin])%mod;
            }
        }
    }
    ///cout<<ans<<'\n';
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            bitset<Nmax> comb=(b[i]&b[j]);
            int cont=comb.count();
            cont=(cont*(cont-1)/2)%mod;
            //for(int k=1;k<=m;k++) cout<<comb[k]<<' ';
            ///cout<<'\n';
            ///cout<<i<<' '<<j<<' '<<cont<<'\n';
            ans=(ans+mod-8*cont%mod)%mod;
        }
    }
    cout<<ans<<'\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...