AcWing 1065. 涂抹果酱
原题链接
简单
作者:
metalRo
,
2022-04-20 17:09:16
,
所有人可见
,
阅读 211
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 1;
const int mod = 1e6;
#define ll long long
ll f[N][251];
ll mp[N];
ll n, m, k, cnt;
ll sta;
ll st[N];
bool check(ll x) //判断该行是否合法
{
ll tmp =-1;//当前的数
ll last = -1;//前一个数
for(int i = 1; i <= m; i++)
{
tmp = x % 3;
if(tmp == last) return false;
x /= 3;
last = tmp;
}
return true;
}
ll quick_power(ll a, ll b)
{
ll res = 1;
while(b)
{
if(b & 1) res = 1ll * a * res;
b >>= 1;
a = a * a * 1ll;
}
return res;
}
bool judge(ll a, ll b)
{
for(int i = 1; i <= m; i++)
{
if(a % 3 == b % 3 )return false;
a /= 3;
b /= 3;
}
return true;
}
int main()
{
cin >> n >> m;
cin >> k;
for(int i = 1; i <= m; i++)
{
cin >> mp[i];
sta = sta * 3 + mp[i] - 1;//将第k行压入一个数中, sta为第k行压缩后得到的数;
}
ll maxx = quick_power(3, m); //找出压位之后最大能得到的数
cnt = 0;
for(int i = 0; i < maxx; i++)
{
if(check(i))//若合法, 则存下来;
{
st[++cnt] = i;
}
}
//cnt表示合法的数一共有多少个
ll pos = -1;
for(int i = 1; i <= cnt; i++)
{
if(st[i] == sta)
{
pos = i;//记录第k行是否合法
break;
}
}
if(pos == -1)//若不合法, 直接判断;
{
puts("0");
return 0;
}
f[k][pos] = 1;
for(int i = k - 1; i >= 1; i--)//判断k以上的行
for(int j = 1; j <= cnt; j++)
for(int k = 1; k <= cnt; k++)
if(judge(st[j], st[k])) //若第j和第k个数是合法的
f[i][j] = (f[i][j] + f[i + 1][k]) % mod;//由i下面的行得到
//同理
for(int i = k + 1;i <= n; i ++)//判断k以下的行
for(int j = 1;j <= cnt; j ++)
for(int k = 1;k <= cnt; k ++)
if(judge(st[j], st[k]))
f[i][j] = (f[i][j] + f[i - 1][k]) % mod;
ll ans1 = 0;
ll ans2 = 0;
for(int i = 1; i <= cnt; i++)
ans1 = (ans1 + f[1][i]) % mod;
for(int i = 1; i <= cnt; i++)
ans2 = (ans2 + f[n][i]) % mod;
if(k == 1)
{
printf("%lld\n", ans2);
}
else if(k == n)
{
printf("%lld\n", ans1);
}
else printf("%lld\n", ans1 * ans2 % mod);
return 0;
}