제출 #1300928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300928		Faisal_Saqib	Šarenlist (COCI22_sarenlist)	C++20	0 / 110	1095 ms	572 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=70,mod=1e9+7;
int d[N][N];
int f(int x)
{
  return ((x*(x-1))/2)%mod;
}
int powmod(int x,int y)
{
  int ans=1;
  while(y)
  {
    if(y&1)ans=(ans*x)%mod;
    // cout<<x<<' '<<y<<' '<<ans<<endl;
    y>>=1;
    x*=x;
    x%=mod;
  }
  return ans;
}
int32_t main()
{
  ios::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  int n,m,k;
  cin>>n>>m>>k;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      d[i][j]=1e9*(i!=j);
    }
  }
  for(int i=1;i<n;i++)
  {
    int x,y;
    cin>>x>>y;
    d[x][y]=1;
    d[y][x]=1;
  }
  for(int m=1;m<=n;m++)
  {
    for(int s=1;s<=n;s++)
    {
      for(int e=1;e<=n;e++)
      {
        d[s][e]=min(d[s][e],d[s][m]+d[m][e]);
      }
    }
  }
  int ways=1;
  int rem=n-1;
  while(m--)
  {
    int x,y;
    cin>>x>>y;
    int t=d[x][y];
    // cout<<t<<' '<<f(t)<<' '<<k<<' '<<f(k)<<endl;
    rem-=2;
    ways*=f(t);
    ways%=mod;
    ways*=f(k);
    ways%=mod;
    ways*=2;
    ways%=mod;
  }
  cout<<(ways*powmod(k,rem))%mod<<endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 65