简化题意
有 \(n\) 个人拿红蓝两色球。每一个人只能拿一种颜色的球。
对于第 \(i\) 个人，最多只能拿 \(a_i\) 个红球，\(b_i\) 个蓝球，但不可以不拿。
接下来有 \(q\) 个操作，每一次选择某个人（输入给定），改变两个值。具体为输入 \(p,A,B\) ，表示将 \(a_p\xleftarrow{}A,b_p\xleftarrow{}B\)，注意的是，修改一直生效。
问至少有 \(C\) 个人拿了红球的总方案数为多少？在每一次操作完后输出，但开头不必输出。（答案 \(\bmod \ 10007\)）
范围
\(n,q\le 10^5\)，\(C\le 20\)。
\(a_i,b_i\le 10^9\)。
分析
Step1:
考虑动态规划。
设状态 \(f_{i,j}\) 表示前 \(i\) 个人中，有 \(j\) 个人选择了红球的方案数。
接下来分析怎样转移得到。
-
假设第 \(i\) 个人拿的是红球，那么就有 \(a_i\) 种情况（因为这个人能拿 \(1\thicksim a_i\) 个红球），那么这种状态就是从 \(f_{i-1,j-1}\) 转移过来。
-
假设第 \(i\) 个人拿的是蓝球，那么就有 \(b_i\) 种情况，那么这种状态就是从 \(f_{i-1,j}\) 转移过来。
根据方案数的加法原理和乘法原理，得到转移为：
\[f_{i,j}=f_{i-1,j-1}\times a_i+f_{i-1,j}\times b_i \]所以我们需要求的答案就是：
\[\sum^{n}_{i=C}f_{n,i} \]空间复杂度为 \(O(n^2)\)，时间复杂度为 \(O(qn^2)\)。
Step2:
我们发现，\(C\le 20\) 这个关键条件一直没有被用到。
尝试使用求补集的方法，即用总方案-不合法方案。
对于第 \(i\) 个人，既能拿红球，也能拿蓝球，所以第 \(i\) 个人就有 \(a_i+b_i\) 种情况。所以总方案为：
\[\prod^{n}_{i=1}(a_i+b_i) \]那么不合法的方案自然是拿红球的人数 \(<C\) 了，所以不合法方案为：
\[\sum^{C-1}_{i=0}f_{n,i} \]空间复杂度为 \(O(nC)\)，时间复杂度为 \(O(qnC)\)。如果考虑本题的时限为 \(10s\) ，应该可以通过此题。
（upd:发现这个复杂度高达 \(10^{10}\)，应该还是过不了）
Step3:
考虑使用线段树维护。
思路和动态规划一样，但是那么既然需要修改，那么我们也需要一些数据结构。
对于每一个叶子节点 \(t\) 都是一个结构体。
struct data{ll f[25];};//f[i]表示该节点所代表的区间拿了i个红球的方案数
维护的 up 函数，我们也是通过加法原理和乘法原理、和两个子节点的信息来维护。具体就是这样：
for(int i=20;i>=0;i--)
{
t[k].f[i]=0;
for(int j=i;j>=0;j--)
t[k].f[i]=(t[k].f[i]+t[ls].f[j]*t[rs].f[i-j])%mod;
}
同时，这颗线段树还需要维护总方案，即
\[\prod^{n}_{i=1}(a_i+b_i) \]搞定这些，你就能 \(\color{green}\texttt{AC}\) 这题了。
放一下代码吧（67行）：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
const ll mod=10007;
int n,C,q;
ll a[N],b[N];
struct data{ll f[25];};//f[i]表示该节点所代表的区间拿了i个红球的方案数
struct Seg1
{
data t[N<<2];ll mul[N<<2];
void up(int k)
{
int ls=k<<1,rs=ls|1;
for(int i=20;i>=0;i--)
{
t[k].f[i]=0;
for(int j=i;j>=0;j--)
t[k].f[i]=(t[k].f[i]+t[ls].f[j]*t[rs].f[i-j])%mod;
}
mul[k]=(mul[ls]*mul[rs])%mod;
}
void build(int k,int l,int r)
{
if(l==r)
{
t[k].f[1]=a[l]%mod;
t[k].f[0]=b[l]%mod;
mul[k]=(a[l]+b[l])%mod;
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
up(k);
}
void upd(int k,int l,int r,int u)
{
if(l==r)
{
t[k].f[1]=a[l]%mod;
t[k].f[0]=b[l]%mod;
mul[k]=(a[l]+b[l])%mod;
return;
}
int mid=(l+r)>>1;
if(u<=mid)upd(k<<1,l,mid,u);
else upd(k<<1|1,mid+1,r,u);
up(k);
}
}T;
int main(){
scanf("%d%d",&n,&C);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
T.build(1,1,n);
scanf("%d",&q);
while(q--)
{
int p;
scanf("%d",&p);scanf("%lld%lld",&a[p],&b[p]);
T.upd(1,1,n,p);
ll ans=0;
for(int i=0;i<C;i++)ans=(ans+T.t[1].f[i])%mod;
printf("%lld\n",((T.mul[1]-ans)%mod+mod)%mod);
}
return 0;
}
最终时间复杂度为 \(O(q\log nC^2)\)，空间复杂度为 \(O(nC)\)。
标签：方案,红球,T6,复杂度,int,NHOI,2016,ll,mod From： https://www.cnblogs.com/DaYanZaiHappy/p/17091033.html