NC173. 填充数组
描述
牛妹给了牛牛一个长度为 的下标从
开始的正整型数组
，粗心的牛牛不小心把其中的一些数字删除了。
假如被删除了，则
。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得：
函数传入一个下标从开始的数组
和一个正整数
，请返回合法的填充方案数对
取模的值,保证不存在方案数为0的数据。
示例1
输入:
[0,4,5],6
输出:
4
说明:
所有的合法填充方案是：[1,4,5],[2,4,5],[3,4,5],[4,4,5]，共4种。示例2
输入:
[1,0,0],3
输出:
6
说明:
所有的合法填充方案是：[1,1,1],[1,1,2],[1,2,2],[1,2,3],[1,3,3],[1,1,3]共6种示例3
输入:
[0,0,0,0,0,67,0,0],100
输出:
746845806
C++ 解法, 执行用时: 3ms, 内存消耗: 428KB, 提交时间: 2021-11-24
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @param k int整型
* @return int整型
*/
int FillArray(vector<int>& a, int k) {
int size=a.size();
int64_t total=1;
int idx=0;
while(idx<size) {
while(idx<size && a[idx]!=0) {
++idx;
}
if(idx==size) break;
int start=idx;
int sval=1;
if(idx>0) sval=a[idx-1];
while(idx<size && a[idx]==0) {
++idx;
}
int end=idx;
int eval=k;
if(idx<size) {
eval=a[idx];
}
total*=calu(eval-sval+1, end-start);
total%=mod;
}
return total;
}
private:
static const int mod=1000000007;
int calu(int nums, int len) {
vector<int> total(len+1, 1);
for(int i=2;i<=nums;++i) {
total[1]=i;
for(int j=2;j<=len;++j) {
total[j]+=total[j-1];
total[j]%=mod;
}
}
return total[len];
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-01-23
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @param k int整型
* @return int整型
*/
int FillArray(vector<int>& a, int k)
{
long sum = 1;
int preIdx = 0;
int curIdx = 0;
for(curIdx = 0, preIdx = 0; curIdx<a.size(); ++curIdx)
{
if(a[curIdx] == 0)
continue;
else
{
if(curIdx - preIdx > 0)
{
int preVal = preIdx==0 ? a[curIdx] : a[curIdx] - a[preIdx - 1] + 1;
sum *= calc(curIdx - preIdx, preVal);
sum %= 1000000007;
preIdx = curIdx;
}
++preIdx;
}
}
if(curIdx - preIdx > 0)
{
sum *= calc(curIdx - preIdx, k - a[preIdx-1] +1);
sum %= 1000000007;
}
return sum;
//return calc(5,4);
}
int calc(int size, int range)
{
if(range == 1) return 1;
if(size == 1) return range;
vector<int> sumVal(range+1, 1);
int sum = range;
for(int i=2; i<=size+1; ++i)
{
for(int j =2; j<=range; ++j)
{
sumVal[j] += sumVal[j-1];
sumVal[j] %= 1000000007;
}
}
return sumVal[range];
}
};
class Solution1 {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @param k int整型
* @return int整型
*/
int FillArray(vector<int>& a, int k)
{
long sum = 1;
int preIdx = 0;
int curIdx = 0;
for(curIdx = 0, preIdx = 0; curIdx<a.size(); ++curIdx)
{
if(a[curIdx] == 0)
continue;
else
{
if(curIdx - preIdx > 0)
{
int preVal = preIdx==0 ? a[curIdx] : a[curIdx] - a[preIdx - 1] + 1;
sum *= calc(curIdx - preIdx, preVal);
sum %= 1000000007;
preIdx = curIdx;
}
++preIdx;
}
}
if(curIdx - preIdx > 0)
{
sum *= calc(curIdx - preIdx, k - a[preIdx-1] +1);
sum %= 1000000007;
}
return sum;
}
//have something wrong: 22/25通过
int calc(int size, int range)
{
if(range == 1) return 1;
if(size == 1) return range;
vector<int> subtract(range, 1);
int sum = range;
int curVal = 0;
int nexVal = 0;
for(int i=2; i<=size; ++i)
{
int levelSum = 0;
curVal = sum % 1000000007;
for(int j =1; j<=range-1; ++j)
{
if(levelSum < 0)
{
int a = 1;
int b =2;
b += a;
}
levelSum +=curVal;
levelSum %= 1000000007;
nexVal = curVal % 1000000007 - subtract[j]% 1000000007;
subtract[j] = curVal % 1000000007;
curVal = nexVal % 1000000007;
}
levelSum += curVal;
levelSum %= 1000000007;
sum = levelSum;
}
return sum;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 432KB, 提交时间: 2021-12-23
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @param k int整型
* @return int整型
*/
static const int mod = 1000000007;
int calu(int nums,int len)
{
vector<int> total(len+1,1);
for (int i = 2;i<=nums;i++)
{
total[1] = i;
for (int j = 2;j <=len;j++)
{
total[j] += total[j-1];
total[j] %= mod;
}
}
return total[len];
}
int FillArray(vector<int>& a, int k) {
int size=a.size();
int64_t total=1;
int idx=0;
while(idx<size) {
while(idx<size && a[idx]!=0) {
++idx;
}
if(idx==size) break;
int start=idx;
int sval=1;
if(idx>0) sval=a[idx-1];
while(idx<size && a[idx]==0) {
++idx;
}
int end=idx;
int eval=k;
if(idx<size) {
eval=a[idx];
}
total*=calu(eval-sval+1, end-start);
total%=mod;
}
return total;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 436KB, 提交时间: 2021-12-09
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @param k int整型
* @return int整型
*/
typedef long long ll;
const ll mod = 1e9 + 7;
ll fpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int FillArray(vector<int> &a, int k) {
// write code here
int len = a.size() + k + 1;
vector<int> c(len, 1), inv(len, 1);
ll sum = 1;
int minn = 1;
for (int i = 1; i < len; ++i) c[i] = 1ll * c[i - 1] * i % mod;
inv[len - 1] = fpow(c[len - 1], mod - 2);
for (int i = len - 2;i > 0;--i) inv[i] = inv[i + 1] * (i + 1ll) % mod;
for (int i = 0; i < a.size(); ++i) {
if (a[i]) {
minn = a[i];
} else {
int cnt = 0;
while (!a[i] && i < a.size()) {
cnt++;
i++;
}
if (i == a.size()) a.emplace_back(k);
int n = (a[i] ? a[i] : k) - minn + 1, m = cnt;
sum *= 1ll * c[n + cnt - 1] * inv[cnt] % mod * inv[n - 1] % mod;
sum %= mod;
minn = a[i];
}
}
return sum;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 452KB, 提交时间: 2022-07-05
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param a int整型vector
* @param k int整型
* @return int整型
*/
int FillArray(vector<int>& a, int k) {
// write code here
vector<long long>res;
long long ans=1,mod=1000000007;
a.insert(a.begin(),1);
a.push_back(k);
long len=a.size(),l=0,r=0;
for(long i=0;i<len;i++)
{
if(a[i]==0)
{
l=i-1;
while(a[i]==0)
i++;
r=i;
vector<long long>dp(a[r]-a[l]+1,1);
for(long j=r-l-1;j>0;j--)
{
for(long long t=a[r]-a[l]-1;t>=0;t--)
{
dp[t]=(dp[t]+dp[t+1])%mod;
}
}
res.push_back(dp[0]%mod);
}
}
for(long i=0;i<res.size();i++)
ans=(ans*res[i])%mod;
return ans;
}
};