Description
给出一个类似杨辉三角的三角形,要求在上边选出m条走n步的路径,并满足:
1. 每条路径只能往左下/右下走,;
2. 第i+1条路径必须在第i条路径的右侧(可以重合);
在给出一些要求,规定第x条路径的第y步一定往左下/右下走。
求方案数
mod109+7
mod
10
9
+
7
Solution
题意转化:构造m个n位二进制数,设 si,x s i , x 表示第i个数前x位有多少个为1,则构造的数要满足 si,j≤si+1,j s i , j ≤ s i + 1 , j ,
O(n22n) O ( n 2 2 n ) 的DP显然,考虑优化,
我们看100101这个数对那些数有贡献,
100101
101001
110001
110010
110011…..
发现,每次相当于把一个1往前移动,或者添加一个1,
考虑用这个来优化,
设f[i][j][S]表示做到第i个数,当前数的前j位和S的前j位一样,
转移:
当前数第j位要为1,s第j位也为1,直接转移到j+1;
0同理,
当前数第j位要为0,s第j位为1,不合法;
当前数第j位要为1,s第j位为0,
那么,就找到s在第j位以后的第一个1,把它变成0,再把第j位变成1,(前移)
如果后面没有,就之间吧第j位变成1(添加)
这样每做一个数,答案就是f[i][n][s],
复杂度: O(n22n) O ( n 2 2 n )
Code
#include <cstdio>
#include <cstdlib>
#define fo(i,a,b) for(register int i=a;i<=b;++i)
#define fod(i,a,b) for(register int i=a;i>=b;--i)
using namespace std;
const int N=22,mo=1e9+7;
int read(int &n)
{
char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n,m1,ans;
int a[N][N];
int f[2][N][1<<20];
int er[N+10];
int zx[1<<21][22];
int main()
{
freopen("!.in","r",stdin);
// freopen(".out","w",stdout);
int q,w,e;
er[1]=1;fo(i,2,22)er[i]=er[i-1]<<1;
read(n),read(m),read(m1);--n;
fo(i,1,m1)read(q),read(w),a[q][w]=1+read(e);
fo(i,0,er[n+1]-1)
{
q=0;
fod(j,n,1)if(er[j]&i)q=j;
else zx[i][j-1]=q;
}
f[0][n][0]=1;
fo(i,1,m)
{
register int I=i&1,q;
fo(j,0,er[n+1]-1)f[I][0][j]=f[!I][n][j],f[!I][n][j]=0;
fo(j,0,n-1)
{
fo(k,0,er[n+1]-1)if(f[I][j][k])
{
if(!a[i][j+1]||a[i][j+1]-1==((k&er[j+1])>>j))((f[I][j+1][k]+=f[I][j][k])>=mo?f[I][j+1][k]-=mo:0);
if(!(k&er[j+1])&&a[i][j+1]!=1)
{
q=k+er[j+1]-er[zx[k][j]];
((f[I][j+1][q]+=f[I][j][k])>=mo?f[I][j+1][q]-=mo:0);
}
f[I][j][k]=0;
}
}
}
fo(i,0,er[n+1]-1)((ans+=f[m&1][n][i])>=mo?ans-=mo:0);
printf("%d\n",ans);
return 0;
}