LOJ AC,luogu WA 求助
查看原帖
LOJ AC,luogu WA 求助
704234
Sad_Rex楼主2025/2/8 11:28
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define Re char y_y
#define rint register int
#define tam cerr << 1e3 * clock ( ) / CLOCKS_PER_SEC << 'm' << 's' << ' ' << ( &y_y - &x_x ) / 1024.0 / 1024.0 << 'M' << 'B' << '\n' , 0
char x_x;
const int N = 4e5 + 5 , mod = 1e9 + 7;
char buf[ 1 << 23 ] , *p1 = buf , *p2 = buf , obuf[ 1 << 23 ] , *p3 = obuf;
#define getchar( ) ( p1 == p2 && ( p2 = ( p1 = buf ) + fread( buf , 1 , 1 << 23 , stdin ) , p1 == p2 ) ? EOF : *p1 ++ )
#define putchar( x ) ( p3 - obuf < 1 << 23 ) ? ( *p3 ++ = x ) : ( fwrite ( obuf , p3 - obuf , 1 , stdout ) , p3 = obuf , * p3 ++ = x )
template < class T >
inline void read ( T & s )
{
  s = 0; 
  bool q = false;
  char c = getchar ();
  while ( ! isdigit ( c ) ) { if (c == '-') q = true; c = getchar (); }
  while (isdigit (c) ) { s = (s << 1) + (s << 3) + (c ^ 48); c = getchar (); }
  if (q) s = -s;
}
template < class T , class ...Args >
inline void read ( T &s , Args &...x ) { read ( s ) , read ( x... ); }
#define pc putchar
stack < char > so;
template <class S>
inline void print ( S x )
{
  if ( x == 0 ) return pc ( '0' ) , pc ( ' ' ) , void ();
  if ( x < 0 ) x = - x , pc ( '-' );
  while ( x ) { so. push ( x % 10 + 48 ) , x /= 10; }
  while ( ! so. empty () ) pc ( so. top () ) , so. pop ();
  putchar ( ' ' );
}
template <class S , class ...Args>
inline void print ( S x , Args ...y ) { print ( x ) , print ( y ... ); }
#undef pc
inline void flush ( ) { fwrite ( obuf , p3 - obuf , 1 , stdout ) , p3 = obuf; }
#define endl putchar ( '\n' )
void add ( int & x , int y ) { ( ( x += y ) >= mod ) && ( x -= mod ); }
void readstr ( string & s )
{
  s = "";
  char c = getchar ( );
  while ( ! ( isdigit ( c ) || c == '<' || c == '>' || c == '?' || c == '(' || c == ')' ) ) c = getchar ();
  while ( ( isdigit ( c ) || c == '<' || c == '>' || c == '?' || c == '(' || c == ')' ) ) s += c , c = getchar ();
}
namespace CharTree
{
  string s; int n; stack < int > st;
  int pos[ N ];
  int ls[ N ] , rs[ N ]; int cnt; char ch[ N ];
  void init ( string str , int _n )
  {
    n = _n , s = str;
    while ( st. size () ) st. pop ();
    for ( rint i = 1 ; i <= n ; i ++ ) pos[ i ] = 0;
    for ( rint i = 1 ; i <= n ; i ++ ) if ( s[ i ] == ')' || s[ i ] == '(' )
    {
      if ( s[ i ] == '(' )
        st. push ( i );
      else
        pos[ i ] = st. top () , st. pop ();
    }
    for ( rint i = 1 ; i <= cnt ; i ++ )
      ls[ i ] = rs[ i ] = 0;
    cnt = 0;
  }
  int build ( int lt , int rt )
  {
    // cerr << lt << ' ' << rt << '\n';
    if ( lt > rt ) return 0;
    if ( lt == rt ) 
    {
      ++ cnt;
      ch[ cnt ] = s[ lt ];
      return cnt;
    }
    if ( pos[ rt ] ) 
    {
      if ( lt == pos[ rt ] ) return build ( lt + 1 , rt - 1 );
      int p = ++ cnt;
      ch[ p ] =  s[ pos[ rt ] - 1 ];
      ls[ p ] = build ( lt , pos[ rt ] - 2 );
      rs[ p ] = build ( pos[ rt ] + 1 , rt - 1 );
      return p;
    }
    else
    {
      int p = ++ cnt;
      ch[ p ] =  s[ rt - 1 ];
      ls[ p ] = build ( lt , rt - 2 );
      rs[ p ] = build ( rt , rt );
      return p;
    }
  }
  int Stat;
  int f[ N ][ 2 ];
  void dfs ( int x , int fa )
  {
    f[ x ][ 0 ] = f[ x ][ 1 ] = 0;
    if ( ch[ x ] >= 48 && ch[ x ] <= 57 ) 
    {
      f[ x ][ ( Stat & ( 1 << ch[ x ] - 48 ) ) == 0 ] = 1;
      // cerr << x << '\n';
      return;
    }
    if ( ! x ) return;
    dfs ( ls[ x ] , x );
    dfs ( rs[ x ] , x );
    if ( ch[ x ] == '<' || ch[ x ] == '?' )
    {
      for ( rint i = 0 ; i < 2 ; i ++ )
      {
        for ( rint j = 0 ; j < 2 ; j ++ )
        {
          for ( rint k = 0 ; k < 2 ; k ++ ) if ( min ( j , k ) == i )
            add ( f[ x ][ i ] , 1ll * f[ ls[ x ] ][ j ] * f[ rs[ x ] ][ k ] % mod ); 
        }
      }
    }
    if ( ch[ x ] == '>' || ch[ x ] == '?' )
    {
      for ( rint i = 0 ; i < 2 ; i ++ )
      {
        for ( rint j = 0 ; j < 2 ; j ++ )
        {
          for ( rint k = 0 ; k < 2 ; k ++ ) if ( max ( j , k ) == i )
            add ( f[ x ][ i ] , 1ll * f[ ls[ x ] ][ j ] * f[ rs[ x ] ][ k ] % mod ); 
        }
      }
    }
  }
}
int n , m;
int a[ N ][ 11 ]; 
string s;
int f[ 1024 ];
int b[ 11 ];
Re; signed main ()
{ 
  read ( n , m );
  iota ( b + 1 , b + 10 , 1 );
  for ( rint i = 0 ; i < m ; i ++ )
    for ( rint j = 1 ; j <= n ; j ++ )
      read ( a[ j ][ i ] );
  readstr ( s ); int len = s. size (); s = ' ' + s;
  CharTree :: init ( s , len ); CharTree :: build ( 1 , len );
  for ( rint i =  0 ; i < ( 1 << m ) ; i ++ )
  {
    CharTree :: Stat = i;
    CharTree :: dfs ( 1 , 0 );
    f[ i ] = CharTree :: f[ 1 ][ 1 ];
    // cerr << f[ i ] << '\n';
  }
  int ans;
  for ( rint i = 1 ; i <= n ; i ++ )
  {
    sort ( b , b + m , [ & ] ( int x , int y ) { return a[ i ][ x ] < a[ i ][ y ]; } );
    int z = 0;
    for ( rint j = 0 ; j < m ; j ++ )
    {
      add ( ans , 1ll * a[ i ][ b[ j ] ] * ( f[ z ] - f[ z | ( 1 << b[ j ] ) ] + mod ) % mod );
      // cerr << f[ z ] - f[ z | ( 1 << b[ j ] ) ] << ' ' << a[ i ][ b[ j ] ] << '\n';
      z |= ( 1 << b[ j ] );
    }
  }
  print ( ans );
  return flush ( ) , 0;
}
2025/2/8 11:28
加载中...