Submission #1365825
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
template<int MOD>
struct ModInt {
static const int Mod = MOD;
unsigned x;
ModInt() : x(0) { }
ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;
int main() {
int N; int M;
while (~scanf("%d%d", &N, &M)) {
vector<int> graph(N);
rep(i, M) {
int u; int v;
scanf("%d%d", &u, &v), -- u, -- v;
graph[u] |= 1 << v;
}
vector<int> popcount(1 << N);
rep(i, 1 << N) rep(j, N)
popcount[i] += i >> j & 1;
vector<mint> pow2s(N + 1);
pow2s[0] = 1;
rer(i, 1, N)
pow2s[i] = pow2s[i - 1] * 2;
//後ろから考える
vector<mint> dp(1 << N);
dp[0] = 1;
rep(S, 1 << N) {
mint x = dp[S];
if (x.x == 0) continue;
int rem = (1 << N) - 1 - S;
for (int T = rem; T > 0; (-- T) &= rem) {
if ((T & 3) == 3) continue;
int U = rem - T;
mint y = x;
rep(i, N) if (S >> i & 1)
y *= pow2s[popcount[graph[i] & T]];
rep(i, N) if (U >> i & 1)
y *= pow2s[popcount[graph[i] & T]] - 1;
dp[S | T] += y;
}
}
mint ans = dp.back();
printf("%d\n", ans.get());
}
return 0;
}
Submission Info
Submission Time
2017-06-19 21:31:49+0900
Task
F - Games on DAG
User
anta
Language
C++14 (GCC 5.4.1)
Score
1600
Code Size
2369 Byte
Status
AC
Exec Time
314 ms
Memory
512 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:36:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &u, &v), -- u, -- v;
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1600 / 1600
Status
Set Name
Test Cases
Sample
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt
Case Name
Status
Exec Time
Memory
0_00.txt
AC
1 ms
256 KB
0_01.txt
AC
1 ms
256 KB
0_02.txt
AC
1 ms
256 KB
0_03.txt
AC
1 ms
256 KB
1_00.txt
AC
1 ms
256 KB
1_01.txt
AC
4 ms
512 KB
1_02.txt
AC
4 ms
512 KB
1_03.txt
AC
313 ms
512 KB
1_04.txt
AC
301 ms
512 KB
1_05.txt
AC
314 ms
512 KB
1_06.txt
AC
106 ms
512 KB
1_07.txt
AC
296 ms
512 KB
1_08.txt
AC
314 ms
512 KB
1_09.txt
AC
301 ms
512 KB
1_10.txt
AC
309 ms
512 KB
1_11.txt
AC
218 ms
512 KB
1_12.txt
AC
312 ms
512 KB
1_13.txt
AC
312 ms
512 KB
1_14.txt
AC
313 ms
512 KB
1_15.txt
AC
246 ms
512 KB
1_16.txt
AC
218 ms
512 KB
1_17.txt
AC
314 ms
512 KB
1_18.txt
AC
104 ms
512 KB
1_19.txt
AC
313 ms
512 KB
1_20.txt
AC
8 ms
512 KB
1_21.txt
AC
2 ms
256 KB
1_22.txt
AC
90 ms
512 KB
1_23.txt
AC
94 ms
512 KB
1_24.txt
AC
8 ms
384 KB
1_25.txt
AC
1 ms
256 KB
1_26.txt
AC
199 ms
512 KB
1_27.txt
AC
5 ms
256 KB
1_28.txt
AC
4 ms
512 KB
1_29.txt
AC
33 ms
256 KB
1_30.txt
AC
1 ms
256 KB
1_31.txt
AC
291 ms
512 KB
1_32.txt
AC
33 ms
256 KB
1_33.txt
AC
4 ms
256 KB
1_34.txt
AC
33 ms
384 KB
1_35.txt
AC
32 ms
256 KB