QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#248974 | #7514. Clique Challenge | urosk | WA | 1ms | 3568kb | C++11 | 3.4kb | 2023-11-11 23:16:41 | 2023-11-11 23:16:41 |
Judging History
answer
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
#define mod 1000000007
#define maxn 1005
ll add(ll x,ll y){
x+=y;
if(x<0){
x%=mod;
x+=mod;
}else{
if(x>=mod) x%=mod;
}
return x;
}
ll mul(ll a,ll b){
ll ans = (a*b)%mod;
if(ans<0) ans+=mod;
return ans;
}
ll n,m;
vector<ll> g[maxn];
ll b[maxn];
ll deg[maxn];
bool cmp(ll x,ll y){
return deg[x]<deg[y];
}
bitset<maxn> gr[maxn];
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> m;
for(ll i = 1;i<=n;i++) gr[i][i] = 1;
for(ll i = 1;i<=m;i++){
ll x,y; cin >> x >> y;
g[x].pb(y);
gr[x][y] = gr[y][x] = 1;
g[y].pb(x);
deg[x]++; deg[y]++;
}
ll ans = 0;
iota(b+1,b+1+n,1);
for(ll i = 1;i<=n;i++){
sort(b+1,b+1+n,cmp);
ll u = b[i];
vector<ll> v;
for(ll s : g[u]){
if(gr[u][s]) v.pb(s);
}
ll c = si(v);
ll cl = c/2,cr = c-cl;
c++;
vector<ll> mask((1<<c));
vector<bool> okl((1<<c));
vector<bool> okr((1<<c));
vector<ll> curl((1<<c));
vector<ll> curr((1<<c));
vector<ll> dp((1<<c));
c--;
//vector<ll> mask((1<<cl));
for(ll i = 0;i<c;i++){
for(ll j = 0;j<c;j++){
if(gr[v[i]][v[j]]) mask[i]|=(1<<j);
}
}
for(ll i = 0;i<(1<<cl);i++){
if(i!=0) curl[i] = (1<<c)-1;
for(ll j = 0;j<cl;j++) if((1<<j)&i) curl[i]&=mask[j];
okl[i] = 1;
for(ll j = 0;j<cl;j++){
if((1<<j)&i){
if(!((1<<j)&curl[i])) okl[i] = 0;
}
}
}
//cer(v);
for(ll i = 0;i<(1<<cr);i++){
if(i!=0) curr[i] = (1<<c)-1;
for(ll j = cl;j<c;j++) if((1<<(j-cl))&i) curr[i]&=mask[j];
okr[i] = 1;
for(ll j = cl;j<c;j++){
if((1<<(j-cl))&i){
if(!((1<<(j))&curr[i])) okr[i] = 0;
}
}
dp[i] = okr[i];
}
for(ll j = 0;j<cr;j++){
for(ll i = 0;i<(1<<cr);i++){
if((1<<j)&i) dp[i]+=dp[i^(1<<j)];
}
}
for(ll i = 0;i<(1<<cl);i++){
ll k = 0;
for(ll j = cl;j<c;j++) if((1<<j)&curl[i]) k|=(1<<(j-cl));
if(okl[i]) ans = add(ans,dp[k]);
}
for(ll s : g[u]){
if(!gr[s][u]) continue;
deg[s]--;
deg[u]--;
gr[u][s] = gr[s][u] = 0;
}
}
cout<<ans<<endl;
return (0-0);
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3568kb
input:
3 2 1 2 2 3
output:
3
result:
wrong answer 1st lines differ - expected: '5', found: '3'