T1
题面
解题
- 发现 \(k\le7\)，故考虑用容斥定理。设 \(ans_i\) 表示不通过 \(i\) 个必经城市的方案数，则最终的输出答案为 \(ans_0-\sum\limits_{i=1}^{k}(-1)^{k-1}ans_i\)。
- 考虑如何统计 \(ans_i\)。发现总状态数不大于 \(2^k\le2^7\)，故枚举每个必经城市的通过与否，得到每一种状态最后的方案数，进而得到 \(ans_i\)。
- 考虑如何获得每一种状态最后的方案书。设 \(f(i,u)\) 表示第 \(i\) 天在 \(u\) 的方案数，则：\(f(i,u)=\sum\limits_{v 与 u 直接相连}f(i-1,v),\)。暴力枚举时间复杂度超时，选择使用矩阵快速幂加速递推。得到一个状态最后的方案数的时间复杂度为 \(\mathcal O(n^3\log d)\)。
- 时间复杂度为 \(\mathcal O(2^k\times n^3\log d)\)。
代码
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxm=160;
const int maxn=25;
const int MOD=1e9+9;
struct edge
{
int u,v;
} E[maxm];
vector<int> e[maxn];
int n,m,ki,d,mst[maxn],ans[maxn],Ans;
bool vis[maxm];
struct Matrix
{
int lenr,lenc;
int e[maxn][maxn];
Matrix(){lenr=lenc=0;memset(e,0,sizeof(0));}
Matrix operator *(Matrix B)
{
Matrix C;
memset(C.e,0,sizeof(C.e));
C.lenr=lenr,C.lenc=B.lenc;
for(int k=1;k<=lenc;k++)
for(int i=1;i<=lenr;i++)
for(int j=1;j<=B.lenc;j++)
C.e[i][j]=((1ll*C.e[i][j]+1ll*e[i][k]*B.e[k][j]%MOD)%MOD+MOD)%MOD;
return C;
}
int sum()
{
int ansi=0;
for(int i=1;i<=lenr;i++)
for(int j=1;j<=lenc;j++)
ansi=((ansi+e[i][j])%MOD+MOD)%MOD;
return ansi;
}
void print()
{
for(int i=1;i<=lenr;i++)
{
for(int j=1;j<=lenc;j++)
cout<<e[i][j]<<" ";
cout<<endl;
}
}
} I,A,A0;
void buildA()
{
memset(A.e,0,sizeof(A.e));
A.lenr=A.lenc=n;
for(int u=1;u<=n;u++)
{
vector<int>::iterator it;
for(it=e[u].begin();it!=e[u].end();it++)
if(!vis[*it])
{
int ui=E[*it].u,vi=E[*it].v;
if(ui!=u) swap(ui,vi);
A.e[u][vi]=1;
}
}
}
void Init()
{
I.lenr=I.lenc=n;
memset(I.e,0,sizeof(I.e));
for(int i=1;i<=n;i++)
I.e[i][i]=1;
A0.lenr=n,A0.lenc=1;
for(int i=1;i<=n;i++)
A0.e[i][1]=1;
}
Matrix ksm(Matrix A,int b)
{
if(b==0) return I;
if(b==1) return A;
Matrix mid=ksm(A,b>>1);
if(b%2==0) return mid*mid;
else return mid*mid*A;
}
signed main()
{
scanf("%lld%lld%lld%lld",&n,&m,&ki,&d);
Init();
//I.print(),A0.print();
for(int i=1;i<=ki;i++) scanf("%lld",&mst[i]);
for(int i=1;i<=m;i++)
{
int u,v; scanf("%lld%lld",&u,&v);
E[i]=(edge){u,v};
e[u].push_back(i),e[v].push_back(i);
}
for(int st=0;st<(1<<ki);st++)
{
memset(vis,false,sizeof(vis));
int idx=0,curst=st;
for(int i=1;i<=ki;i++)
{
if(curst&1)
{
idx++;
vector<int>::iterator it;
for(it=e[mst[i]].begin();it!=e[mst[i]].end();it++)
vis[*it]=true;
}
curst>>=1;
}
buildA();//cout<<st<<"here\n";//A.print();
Matrix ANS=ksm(A,d-1)*A0;//ANS.print();
ans[idx]=((ans[idx]+ANS.sum())%MOD+MOD)%MOD;
}
int sgn=1;
for(int i=0;i<=ki;i++)
Ans=((Ans+sgn*ans[i]%MOD)%MOD+MOD)%MOD,
//cout<<ans[i]<<" "<<i<<endl;
sgn*=-1;
printf("%lld",Ans%MOD);
return 0;
}
/*
4 4 2 3
1 2
1 2
2 3
3 1
2 4
*/
T2
题面
解题
- 发现每一列的状态只有白白、白黑、黑白三种，且白黑与黑白可实现连续交替存在。故定义白白为白块，白黑与黑白为黑块。
- 假设目前 \(k\) 个黑块连续，则可先将黑块分为 \(i\) 个不相连的连续段，枚举用于划分黑块段的白块段的位置，有 \(C_{k-1}^{i-1}\) 中方案。接下来，将白块插入进序列中，其中应满足两个黑块段之间的白块数不能为 \(0\)，两端黑块段的外则的白块数可以为 \(0\)，故有 \(C_{n-k+1}^{i}\)种方案。在枚举每个黑块段的起始黑块的模式，故最终答案为 \(\sum\limits_{i=1}^{\min(k,n-k+1)}2^iC_{k-1}^{i-1}C_{n-k+1}^{i}\)。