QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#143340#7021. Counting Sheep in Ami DongsuoSortingTL 1ms3744kbC++204.5kb2023-08-21 07:25:312023-08-21 07:25:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-21 07:25:34]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3744kb
  • [2023-08-21 07:25:31]
  • 提交

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()

int test_id ;
const int MAXN = 1e4 + 7 ;
const int MOD = 1e9 + 7 ;
const int MAXW = 402 ;

typedef complex<double> C;
typedef vector<double> vd;
void fft(vector<C>& a) {
	int n = sz(a), L = 31 - __builtin_clz(n);
	static vector<complex<long double>> R(2, 1);
	static vector<C> rt(2, 1);  // (^ 10% faster if double)
	for (static int k = 2; k < n; k *= 2) {
		R.resize(n); rt.resize(n);
		auto x = polar(1.0L, acos(-1.0L) / k);
		rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
	}
	vi rev(n);
	rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
			// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
			auto x = (double *)&rt[j+k], y = (double *)&a[i+j+k];        /// exclude-line
			C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
			a[i + j + k] = a[i + j] - z;
			a[i + j] += z;
		}
}
vd conv(vd& a, vd& b) {
	if (a.empty() || b.empty()) return {};
	vd res(sz(a) + sz(b) - 1);
	int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
	vector<C> in(n), out(n);
	copy(all(a), begin(in));
	rep(i,0,sz(b)) in[i].imag(b[i]);
	fft(in);
	for (C& x : in) x *= x;
	rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
	fft(out);
	rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
	return res;
}

template<int M> vi convMod(const vi &a, const vi &b) {
	if (a.empty() || b.empty()) return {};
	vi res(sz(a) + sz(b) - 1);
	int B=32-__builtin_clz(sz(res)), n=1<<B, cut=int(sqrt(M));
	vector<C> L(n), R(n), outs(n), outl(n);
	rep(i,0,sz(a)) L[i] = C((int)a[i] / cut, (int)a[i] % cut);
	rep(i,0,sz(b)) R[i] = C((int)b[i] / cut, (int)b[i] % cut);
	fft(L), fft(R);
	rep(i,0,n) {
		int j = -i & (n - 1);
		outl[j] = (L[i] + conj(L[j])) * R[i] / (2.0 * n);
		outs[j] = (L[i] - conj(L[j])) * R[i] / (2.0 * n) / (C)1i;
	}
	fft(outl), fft(outs);
	rep(i,0,sz(res)) {
		ll av = ll(real(outl[i])+.5), cv = ll(imag(outs[i])+.5);
		ll bv = ll(imag(outl[i])+.5) + ll(real(outs[i])+.5);
		res[i] = ((av % M * cut + bv) % M * cut + cv) % M;
	}
	return res;
}


int n , m , lim ;
int a[ MAXN ] ;
vector < int > v[ MAXN ] ;
int dp[ MAXN ][ MAXW ] ;

int ans[ 3 * MAXW ] ;

void dfs ( int x ) {
    for ( int i = 0 ; i <= lim ; ++ i ) { dp[ x ][ i ] = 0 ; }
    dp[ x ][ a[ x ] ] = 1 ;
    for ( auto y : v[ x ] ) {
        dfs ( y ) ;
        for ( int j = 0 ; j <= lim ; ++ j ) {
            dp[ x ][ j ] = ( dp[ x ][ j ] + dp[ y ][ j ] ) % MOD ;
        }
    }
}

ll fastpow ( ll x , ll pw ) {
    ll ret = 1 ;
    while ( pw > 0 ) {
        if ( ( pw % 2 ) == 0 ) {
            x = ( x * x ) % MOD ;
            pw /= 2 ;
        }
        else {
            ret = ( ret * x ) % MOD ;
            -- pw ;
        }
    }
    return ret ;
}

void solve ( ) {
    ++ test_id ;
    cout << "Case #" << test_id << ": " ;
    cin >> n >> m >> lim ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
        v[ i ].clear ( ) ;
    }
    for ( int i = 0 ; i <= 3 * lim ; ++ i ) { ans[ i ] = 0 ; }
    for ( int i = 1 , x , y ; i <= m ; ++ i ) {
        cin >> x >> y ;
        v[ x ].push_back ( y ) ;
    }
    dfs ( 1 ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        vi one , two , three ;
        two.resize ( 2 * lim + 1 , 0 ) ;
        three.resize ( 3 * lim + 1 , 0 ) ;
        for ( int j = 0 ; j <= lim ; ++ j ) {
            one.push_back ( dp[ i ][ j ] ) ;
            two[ 2 * j ] = dp[ i ][ j ] ;
            three[ 3 * j ] = dp[ i ][ j ] ;
        }
        vi wtf = convMod < MOD > ( one , one ) ;
        vi aux = convMod < MOD > ( wtf , one ) ;
        vi sub = convMod < MOD > ( two , one ) ;
        for ( int j = 0 ; j <= 3 * lim ; ++ j ) {
            ll add = ( aux[ j ] - 3 * sub[ j ] + 3LL * MOD + 2 * three[ j ] ) % MOD ;
            ans[ j ] = ( ans[ j ] + add ) % MOD ;
        }
    }
    ll inv = fastpow ( 6 , MOD - 2 ) ;
    for ( int i = 1 ; i <= 3 * lim ; ++ i ) {
        cout << ( ans[ i ] * inv ) % MOD ;
        if ( i != 3 * lim ) { cout << " " ; }
    }
    cout << "\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: 1ms
memory: 3744kb

input:

2
4 3 4
1 2 3 4
1 2
1 3
1 4
4 6 4
1 2 3 4
1 2
1 3
1 4
2 3
2 4
3 4

output:

Case #1: 0 0 0 0 0 1 1 1 1 0 0 0
Case #2: 0 0 0 0 0 2 5 9 16 11 13 4

result:

ok 2 lines

Test #2:

score: -100
Time Limit Exceeded

input:

5
9974 29992 400
170 290 309 152 96 55 128 315 95 69 301 193 9 316 45 192 132 360 53 370 342 110 130 228 300 189 293 327 208 306 46 162 280 167 107 163 335 289 330 354 192 44 393 47 185 330 53 278 91 229 194 276 72 159 126 75 48 205 371 263 76 375 309 145 59 186 76 255 73 352 271 318 77 144 27 398 9...

output:


result: