QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #285838 | #7607. The Doubling Game 2 | Sorting | WA | 0ms | 23308kb | C++20 | 5.8kb | 2023-12-16 23:27:26 | 2023-12-16 23:27:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
const int MAXN = 3e5 + 7 ;
const int MOD = 1e9 + 7 ;
const int LOG = 20 ;
int n ;
vector < int > v[ MAXN ] ;
int subtree[ MAXN ] ;
bool cmp ( int x , int y ) {
return ( subtree[ x ] < subtree[ y ] ) ;
}
ll dp[ MAXN ][ LOG ] ; //
ll root[ MAXN ][ LOG ] ; //
ll complete[ MAXN ] ;
int mxpw[ MAXN ] ;
ll f[ ( 1 << LOG ) ][ LOG ] ;
int bit_rv[ 2 * ( 1 << LOG ) ] ;
void dfs ( int x , int prv ) {
vector < int > children ;
for ( auto y : v[ x ] ) {
if ( y == prv ) { continue ; }
dfs ( y , x ) ;
children.push_back ( y ) ;
}
sort ( children.begin ( ) , children.end ( ) , cmp ) ;
mxpw[ x ] = 0 ;
subtree[ x ] = 1 ;
for ( int i = 0 ; i < LOG ; ++ i ) {
f[ 0 ][ i ] = 0 ;
}
f[ 0 ][ LOG - 1 ] = 1 ;
for ( auto y : children ) {
subtree[ x ] += subtree[ y ] ;
int rem = mxpw[ x ] ;
mxpw[ x ] = max ( mxpw[ x ] , min ( mxpw[ x ] + 1 , mxpw[ y ] + 2 ) ) ;
if ( rem < mxpw[ x ] ) {
int lo = ( 1 << rem ) ;
int hi = 2 * lo - 1 ;
for ( int i = lo ; i <= hi ; ++ i ) {
for ( int j = 0 ; j < LOG ; ++ j ) {
f[ i ][ j ] = 0 ;
}
}
}
/**
if ( x == 1 ) {
printf ( "--- child %d\n" , y ) ;
}
**/
for ( int i = ( 1 << mxpw[ x ] ) - 1 ; i >= 0 ; -- i ) {
for ( int j = 0 ; j <= mxpw[ y ] ; ++ j ) {
if ( ( i & ( 1 << j ) ) == 0 ) {
for ( int dig = 0 ; dig <= mxpw[ x ] ; ++ dig ) {
if ( j == dig ) { continue ; }
f[ ( i + ( 1 << j ) ) ][ dig ] = ( f[ ( i + ( 1 << j ) ) ][ dig ] + f[ i ][ dig ] * root[ y ][ j ] ) % MOD ;
/**
if ( x == 1 && i + ( 1 << j ) == 1 && dig == 1 ) {
printf ( "add %lld == %lld * %lld at %d %d %d\n" , f[ i ][ dig ] * root[ y ][ j ] , f[ i ][ dig ] , root[ y ][ j ] , i , j , dig ) ;
}
**/
}
f[ ( i + ( 1 << j ) ) ][ LOG - 1 ] = ( f[ ( i + ( 1 << j ) ) ][ LOG - 1 ] + f[ i ][ LOG - 1 ] * root[ y ][ j ] ) % MOD ;
}
/**
if ( x == 1 && i == 1 && j == 1 ) {
printf ( "add nw %lld idle %lld \n" , f[ i ][ LOG - 1 ] * dp[ y ][ j ] , f[ i ][ j ] * complete[ y ] ) % MOD ;
}
if ( x == 1 && i == 0 && j == 1 ) {
printf ( "add to 0 1 nw %lld idle %lld \n" , f[ i ][ LOG - 1 ] * dp[ y ][ j ] , f[ i ][ j ] * complete[ y ] ) % MOD ;
}
**/
f[ i ][ j ] = ( f[ i ][ LOG - 1 ] * dp[ y ][ j ] + f[ i ][ j ] * complete[ y ] ) % MOD ;
}
f[ i ][ LOG - 1 ] = ( f[ i ][ LOG - 1 ] * complete[ y ] ) % MOD ;
}
}
/**
for ( int i = 0 ; i < ( 1 << mxpw[ x ] ) ; ++ i ) {
for ( int j = 0 ; j <= mxpw[ x ] ; ++ j ) {
printf ( "vertex %d --> f[ %d ][ %d ] = %lld\n" , x , i , j , f[ i ][ j ] ) ;
}
printf ( "vertex %d --> f[ %d ][ -1 ] = %lld\n" , x , i , f[ i ][ LOG - 1 ] ) ;
}
**/
for ( int mask = 0 ; mask < ( 1 << mxpw[ x ] ) ; ++ mask ) {
int lw = bit_rv[ ( ( ~mask ) & -( ~mask ) ) ] ; // smallest 0 bit id
for ( int p1 = 0 ; p1 < LOG ; ++ p1 ) {
if ( ( mask & ( 1 << p1 ) ) > 0 ) { continue ; }
if ( p1 == LOG - 1 ) { //
if ( ( ( mask + ( 1 << lw ) ) & ( mask + ( 1 << lw ) + 1 ) ) == 0 ) {
dp[ x ][ lw ] = ( dp[ x ][ lw ] + f[ mask ][ p1 ] ) % MOD ;
}
if ( ( mask & ( mask + 1 ) ) == 0 ) {
root[ x ][ lw ] = ( root[ x ][ lw ] + f[ mask ][ p1 ] ) % MOD ;
/**
if ( x == 1 ) {
printf ( "-- add %d %d %lld\n" , mask , p1 , f[ mask ][ p1 ] ) ;
}
**/
complete[ x ] = ( complete[ x ] + f[ mask ][ p1 ] ) % MOD ;
}
}
else {
if ( ( mask + ( 1 << lw ) ) == ( 1 << p1 ) - 1 ) {
dp[ x ][ lw ] = ( dp[ x ][ lw ] + f[ mask ][ p1 ] ) % MOD ;
}
if ( mask == ( 1 << p1 ) - 1 ) {
/**
if ( x == 1 ) {
printf ( "-- add %d %d %lld\n" , mask , p1 , f[ mask ][ p1 ] ) ;
}
**/
complete[ x ] = ( complete[ x ] + f[ mask ][ p1 ] ) % MOD ;
}
}
}
}
/**
printf ( "complete[ %d ] = %lld\n" , x , complete[ x ] ) ;
for ( int i = 0 ; i < ( 1 << mxpw[ x ] ) ; ++ i ) {
printf ( "dp[ %d ][ %d ] = %lld\n" , x , i , dp[ x ][ i ] ) ;
printf ( "root[ %d ][ %d ] = %lld\n" , x , i , root[ x ][ i ] ) ;
}
**/
}
void solve ( ) {
cin >> n ;
for ( int i = 1 , x , y ; i < n ; ++ i ) {
cin >> x >> y ;
v[ x ].push_back ( y ) ;
v[ y ].push_back ( x ) ;
}
for ( int i = 0 ; i < 2 * ( 1 << LOG ) ; ++ i ) {
bit_rv[ i ] = -1 ;
}
for ( int i = 0 ; i <= LOG ; ++ i ) {
bit_rv[ ( 1 << i ) ] = i ;
}
dfs ( 1 , -1 ) ;
cout << complete[ 1 ] << "\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ; // cin >> t ;
while ( t -- ) { solve ( ) ; }
return 0 ;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 23308kb
input:
5 1 2 1 3 1 4 4 5
output:
21
result:
ok single line: '21'
Test #2:
score: 0
Accepted
time: 0ms
memory: 23112kb
input:
1
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 23124kb
input:
128 11 32 116 81 65 4 117 47 5 81 104 30 61 8 82 59 95 20 92 29 29 127 97 39 123 33 59 128 115 33 83 67 74 16 77 33 64 73 124 123 8 127 61 51 101 122 35 90 119 116 112 27 81 93 109 123 54 1 119 100 116 16 65 47 67 27 22 105 76 87 36 39 27 96 72 31 91 123 21 105 118 12 110 48 121 72 14 115 24 16 106 ...
output:
206205694
result:
wrong answer 1st lines differ - expected: '508800953', found: '206205694'