QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235557#7607. The Doubling Game 2kkioRE 8ms28840kbC++177.2kb2023-11-02 21:46:502023-11-02 21:46:50

Judging History

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

  • [2023-11-02 21:46:50]
  • 评测
  • 测评结果:RE
  • 用时:8ms
  • 内存:28840kb
  • [2023-11-02 21:46:50]
  • 提交

answer

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast","unroll-loops","inline","no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
namespace Def{
    #define fir first
    #define sec second
    #define lson (tr[i].ls)
    #define rson (tr[i].rs)
    #define FIO(file) freopen(file".in","r",stdin), freopen(file".out","w",stdout)
    #define Untie() ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
    typedef long long ll;
    typedef double db;
    typedef long double ldb;
    typedef unsigned int uint;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    typedef pair<ll,ll> pll;
    typedef __int128_t i128;
}
using namespace Def;
namespace FastIO {
	struct IO {
	    char ibuf[(1 << 20) + 1], *iS, *iT, obuf[(1 << 20) + 1], *oS;
	    IO() : iS(ibuf), iT(ibuf), oS(obuf) {} ~IO() { fwrite(obuf, 1, oS - obuf, stdout); }
		#if ONLINE_JUDGE
		#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
		#else
		#define gh() getchar()
		#endif
		inline bool eof (const char &ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == 't' || ch == EOF; }
	    inline long long read() {
	        char ch = gh();
	        long long x = 0;
	        bool t = 0;
	        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
	        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
	        return t ? ~(x - 1) : x;
	    }
	    inline void read (char *s) {
	    	char ch = gh(); int l = 0;
	    	while (eof(ch)) ch = gh();
	    	while (!eof(ch)) s[l++] = ch, ch = gh();
	    }
	    inline void read (double &x) {
	    	char ch = gh(); bool t = 0;
	    	while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
	    	while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh();
	    	if (ch != '.') return t && (x = -x), void(); ch = gh();
	    	for (double cf = 0.1; '0' <= ch && ch <= '9'; ch = gh(), cf *= 0.1) x += cf * (ch ^ 48);
	    	t && (x = -x);
	    }
	    inline void pc (char ch) {
	    	#ifdef ONLINE_JUDGE
	    	if (oS == obuf + (1 << 20) + 1) fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; 
	    	*oS++ = ch;
	    	#else
	    	putchar(ch);
	    	#endif
		}
        inline void write (char *s)
        {
            int len = strlen(s);
            for(int i = 0; i < len; i++)pc(s[i]);
        }
		template<typename _Tp>
	    inline void write (_Tp x) {
	    	static char stk[64], *tp = stk;
	    	if (x < 0) x = ~(x - 1), pc('-');
			do *tp++ = x % 10, x /= 10;
			while (x);
			while (tp != stk) pc((*--tp) | 48);
	    }
	    inline void puts(const char *s){
			int len = strlen(s);
			for (int i = 0; i < len; i++)pc(s[i]);
		}
	} io;
	inline long long read () { return io.read(); }
	template<typename Tp>
	inline void read (Tp &x) { io.read(x); }
	template<typename _Tp>
	inline void write (_Tp x) { io.write(x); }
}
using namespace FastIO;
namespace misc{
    constexpr int infi=1e9;
    constexpr int minfi=0x3f3f3f3f;
    constexpr ll infl=1e18;
    constexpr ll minfl=0x3f3f3f3f3f3f3f3f;
    constexpr int mod=1e9+7;
    constexpr int inv2=(mod+1)/2;
    constexpr int inv3=(mod+1)/3;
    mt19937_64 rnd(0x3494393);
    template<typename T,typename E>
        inline T ksm(T b,E p){T ret=1;while(p){if(p&1)ret=1ll*ret*b%mod;b=1ll*b*b%mod;p>>=1;}return ret;}
    template<typename T,typename E> 
        inline T ginv(T v){return ksm(v,mod-2);}
    template<typename T,typename E>
        inline void cmax(T &a,E b){a<b?(a=b,1):0;}
    template<typename T,typename E>
        inline void cmin(T &a,E b){a>b?(a=b,1):0;}
    template<typename T,typename E>
        inline void cadd(T &a,E b){(a+=b)>=mod?(a-=mod):0;}
    template<typename T,typename E>
        inline void csub(T &a,E b){(a-=b)<0?(a+=mod):0;}
    template<typename T,typename E>
        inline void cmul(T &a,E b){a=1ll*a*b%mod;}
    template<typename T,typename E>
        inline T madd(T a,E b){return (a+=b)>=mod?(a-mod):a;}
    template<typename T,typename E>
        inline T msub(T a,E b){return (a-=b)<0?(a+mod):a;}
    template<typename T,typename E>
        inline T mmul(T a,E b){return 1ll*a*b%mod;}
    template<typename T>
        struct dseg{T *first,*last;dseg(T* _l,T* _r):first(_l),last(_r){}};
    inline void debug(void){cerr<<'\n';}
    template<typename T,typename... arg>
        inline void debug(T x,arg... r){cerr<<x<<' ';debug(r...);}
    template<typename T,typename... arg>
        inline void debug(dseg<T> A,arg... v){cerr<<"[ ";for(T* i=A.first;i!=A.last;++i)cerr<<*i<<' ';cerr<<"] ";debug(v...);}
    template<typename T>
        inline T randseg(T l,T r){assert(l<=r);return rnd()%(r-l+1)+l;}
    template<typename T>
        inline bool gbit(T v,int bit){return v>>bit&1;}
    inline ll gcd(ll a,ll b){if(!b||!a) return a+b;ll az=__builtin_ctz(a),bz=__builtin_ctz(b),z=(az>bz)?bz:az,t;b>>=bz;while(a) a>>=az,t=a-b,az=__builtin_ctz(t),b=a<b?a:b,a=t<0?-t:t;return b<<z;}
    inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1,y=0;return a;}ll g=exgcd(b,a%b,y,x);y-=x*(a/b);return g;}
    inline ll Sum1(ll n){return n*(n+1)/2;}
    inline ll Sum2(ll n){return n*(n+1)*(2*n+1)/6;}
    inline ll Sqr(ll n){return n*n;}
    #define binom(n,m) (n<0||m<0||n<m?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod)
    #define likely(x) (__builtin_expect(!!(x),1))
    #define unlikely(x) (__builtin_expect(!!(x),0))
}
using namespace misc;
const int maxn=3e5+10;
int n;
vector<int> G[maxn];
vector<int> f[maxn],g[maxn];
int h[maxn];
int dp[2][(1<<17)][2];
void dfs(int u,int fa)
{
    for(int i=0;i<G[u].size();i++)
    {
        if(G[u][i]==fa)swap(G[u].back(),G[u][i]),G[u].pop_back(),i--;
        else dfs(G[u][i],u);
    }
    sort(G[u].begin(),G[u].end(),[&](int a,int b){return f[a].size()<f[b].size();});
    int o=0,nowm=0;dp[0][0][0]=1,dp[0][0][1]=0;
    for(int t=0;t<G[u].size();t++)
    {
        int v=G[u][t],mem=f[v].size();
        for(int S=0;S<(1<<mem);S++)dp[o^1][S][0]=dp[o^1][S][1]=0;
        for(int S=0;S<(1<<nowm);S++)
        {
            cadd(dp[o^1][S][0],mmul(dp[o][S][0],h[v]));
            cadd(dp[o^1][S][1],mmul(dp[o][S][1],h[v]));
            for(int i=0;i<mem;i++)
                if(!gbit(S,i))
                {
                    cadd(dp[o^1][S|(1<<i)][0],mmul(dp[o][S][0],f[v][i]));
                    if(S>(1<<i))cadd(dp[o^1][S|(1<<i)][1],mmul(dp[o][S][1],f[v][i]));
                    else cadd(dp[o^1][S|(1<<i)][1],mmul(dp[o][S][0],g[v][i]));
                }
        }
        nowm=mem;
        
        o^=1;
    }
    int sz=nowm+1;
    f[u].resize(sz),g[u].resize(sz);
    for(int i=0;i<sz;i++)
    {
        int w=(1<<i)-1;
        cadd(h[u],dp[o][w][0]);
        cadd(h[u],dp[o][w][1]);
        cadd(f[u][i],dp[o][w][0]);
        cadd(g[u][i],dp[o][w][0]);
        for(int j=0;j<i-1;j++)cadd(g[u][j],dp[o][w^(1<<j)][0]),cadd(g[u][j],dp[o][w^(1<<j)][1]);
    }
    // debug("!",u);
    // for(int i=0;i<f[u].size();i++)
    //     debug(f[u][i],g[u][i]);
    // debug(h[u]);
}
int main(){
    n=read();
    for(int i=1,u,v;i<n;i++)
    {
        u=read(),v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    write(h[1]),io.pc('\n');
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 26084kb

input:

5
1 2
1 3
1 4
4 5

output:

21

result:

ok single line: '21'

Test #2:

score: 0
Accepted
time: 8ms
memory: 28200kb

input:

1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 3ms
memory: 26116kb

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:

508800953

result:

ok single line: '508800953'

Test #4:

score: 0
Accepted
time: 0ms
memory: 26284kb

input:

256
53 177
57 242
74 90
107 104
209 169
132 70
152 142
71 168
143 99
91 130
202 140
49 165
209 193
209 137
159 188
247 48
49 21
20 208
155 185
120 231
83 87
37 84
143 18
106 8
114 79
191 158
208 256
133 252
215 92
199 108
166 168
39 217
85 69
204 139
100 75
111 6
230 198
79 130
26 155
155 38
55 81
1...

output:

999869740

result:

ok single line: '999869740'

Test #5:

score: 0
Accepted
time: 0ms
memory: 28840kb

input:

512
507 193
168 152
48 369
273 170
101 349
160 261
438 197
446 224
125 264
210 131
272 218
361 85
226 119
57 33
229 89
37 317
130 417
30 470
435 300
499 417
132 260
196 430
119 117
157 260
207 151
368 277
188 371
214 330
484 228
96 94
97 442
251 461
443 248
163 207
306 147
346 90
457 112
436 222
364...

output:

37387055

result:

ok single line: '37387055'

Test #6:

score: -100
Runtime Error

input:

1024
340 598
1 851
245 819
414 736
996 316
300 284
924 407
532 557
362 178
1006 469
397 373
742 77
112 37
406 892
703 666
496 825
1002 100
875 856
263 975
227 6
288 389
661 437
160 626
833 770
912 837
405 628
466 686
45 629
59 13
163 991
1017 422
208 247
344 376
709 956
570 272
996 954
518 454
267 3...

output:


result: