前言
当拿到这道题只想打暴力的时候，我就已经输了。
题目
题目大意
校长 ( t DD(XYX)) 在知乎上开启了隐私保护！为了得知校长的最新动态并跟随他的脚步，他忠诚的追随者们需要破解他的隐私密码。
校长的隐私密码由长达 (N) 位的数码组成，每一位的数码范围为 ([1,K])。
校长的密码并非完全无迹可寻，根据校长的日常用语以及行为准则，他的追随者们得到了 (M) 个信息，每个信息有两个整数 (a_i,b_i) ，表示数码 (a_i) 不会出现在 (b_i) 之前。
为了估算破解密码的时间花费，你需要计算出一共有多少种不同的密码。
同时它的追随者们对每一种密码视为十进制数的算术和很感兴趣，认为这是校长神通广大的原力，所以你也需要计算出来，而且不允许有任何作假！(不取模)
(1le Nle 500;0le Mle 100;Kle 9.)
嘿，小声点，小心被校长发现了！还有，动作快点，(1s) 是极限了！
样例
样例输入1
4 4 3
1 1
1 2
2 2
3 1
样例输出1
7
19020
讲解
这道题 (M=0) 的数据有 (50pts)，加上 (Nle 6) 的 (20pts) 就有 (70pts)，所以完全没打算想正解，佛了。
考试结束后一琢磨，这不是状压+高精板题吗？！
从高位向低位DP可以避免高精乘高精。
时间复杂度 (O(2^KKNC))，其中 (C) 是高精度复杂度。
代码
由于OJ太烂而需要大力卡常还加了Ofast的代码
//12252024832524
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int n,m,k;
LL Read()
{
LL x = 0,f = 1; char c = getchar();
while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Min(T x){return x < 0 ? -x : x;}
const LL N = 100000000000000000ll;
struct BigNum
{
bool hv;
int len;
LL a[145];
BigNum(){memset(a,0,sizeof(a));}
void init(LL x)
{
for(int i = 0;i <= len;++ i) a[i] = 0;
len = -1; hv = 1;
do
{
a[++len] = x%N;
x/=N;
}while(x);
}
BigNum operator + (const BigNum &C)const
{
BigNum ret; ret.len = Max(len,C.len); ret.hv = 1;
LL jw = 0;
for(int i = 0;i <= ret.len;++ i)
{
ret.a[i] = a[i]+C.a[i]+jw;
jw = ret.a[i] / N;
ret.a[i] %= N;
}
while(jw) ret.a[++ret.len] = jw%N,jw/=N;
return ret;
}
BigNum operator * (const LL x)const
{
BigNum ret; LL jw = 0; ret.len = len; ret.hv = 1;
for(int i = 0;i <= len;++ i)
{
ret.a[i] = a[i]*x+jw;
jw = ret.a[i] / N;
ret.a[i] %= N;
}
while(jw) ret.a[++ret.len] = jw%N,jw/=N;
return ret;
}
void operator += (const BigNum &C)
{
LL jw = 0; len = Max(len,C.len); hv = 1;
for(int i = 0;i <= len;++ i)
{
if(!jw && i > C.len) break;
a[i] = a[i]+C.a[i]+jw;
jw = a[i]/N;
a[i] %= N;
}
while(jw) a[++len] = jw%N,jw/=N;
}
void print()
{
if(len < 0) return; Put(a[len]);
for(int i = len-1;i >= 0;-- i) printf("%017lld",a[i]);
putchar('
');
}
};
int fk[10][10];
BigNum cnt[2][1<<9],dp[2][1<<9];
bool can[9][1<<9];
int lowbit(int x){return x & -x;}
int main()
{
freopen("hacker2.in","r",stdin);
freopen("hacker2.out","w",stdout);
n = Read(); m = Read(); k = Read();
for(int i = 1;i <= m;++ i)
{
int u = Read(),v = Read();
fk[u-1][v-1] = 1;
}
int sx = (1<<k) - 1;
for(int S = 0;S <= sx;++ S)
for(int i = 0;i < k;++ i)
{
can[i][S] = 1;
for(int j = 0;j < k;++ j)
if((S >> j & 1) && fk[j][i])
can[i][S] = 0;
}
dp[0][0].init(0); cnt[0][0].init(1);
for(int i = 1;i <= n;++ i)
{
bool now = i&1;
for(int S = 0;S <= sx;++ S) dp[now][S].init(0),cnt[now][S].init(0),dp[now][S].hv = cnt[now][S].hv = 0;
for(int S = 0;S <= sx;++ S)
{
dp[now^1][S]=dp[now^1][S]*10;
for(int j = 0;j < k;++ j)
{
if(!can[j][S] || !cnt[now^1][S].hv) continue;
dp[now][S|(1<<j)] += dp[now^1][S];
dp[now][S|(1<<j)] += cnt[now^1][S]*(j+1);
cnt[now][S|(1<<j)] += cnt[now^1][S];
}
}
}
BigNum ans1,ans2; ans1.init(0); ans2.init(0);
for(int S = 0;S <= sx;++ S) ans1 += cnt[n&1][S],ans2 += dp[n&1][S];
ans1.print(); ans2.print();
return 0;
}