P11362 [NOIP2024] 遗失的赋值 题解
题目链接
我的博客
前言
笔者在考场上隐约感觉到了什么，感知到T2要比T1简单？但是T2一定是一道数学题，因此笔者使劲推了 \(1\) 个小时的式子，最终因为心态直接崩掉，遗憾离场。
直到现在笔者才鼓起勇气，重新征服一下这道题。发现其实真的不难想，确实是一道绿题。这告诉我们——真的心态很重要。。。
补提参考
思路
考虑一个区间内可以放下 \(x\) 个二元限制组合法的方案数，记为 \(F(x)\)。
考虑二元限制的第一个数与左端点相同。此时下一个数也一定有限制。这一种情况有 \(v\) 种可能，下一个数就是 \(F(x-1)\)。因此这类情况总方案数为 \(v \times F(x-1)\)
考虑二元限制的第一个数与左端点不同。因为 \(v > 1\)，所以第二个数一定有方法和第二个二元限制的第一个数不同。所以，只要后面的每次不和二元限制的第一个数相同，都一定有方法把这个区间所有数全部填上。剩下的二元限制方案数为 \((v^2)^{(x-1)}=v^{2x-2}\)，第一个数的方案数为 \(v \times (v-1)\)，相乘得到 \(v \times (v-1) \times v^{2x-2}=v^{2x}-v^{2x-1}\)。
以上两种情况相加记为最终答案。
边界为 \(F(1)=v^2-v+1\)，即二元限制的第一个数与左边的数不同的 \(v(v−1)\) 种情况，加上这两个数相同则右边的两个数也必须相同的 \(1\) 种情况。
将 \(F(x-1)\) 用 \(F(x-2)\) 代入得
将 \(F(x-2)\) 用 \(F(x-3)\) 代入得
于是我们得到了
代入 \(k=x-1\) 得到
最终答案是每两个限制之间的区间的情况数相乘。还需要乘上开头区间和结尾区间的值。
考虑开头。没有左端点的限制，所以可以直接 \(v^{2x}\)。
考虑结尾。没有右端点的限制，也可以直接 \(v^{2x}\)。
代码
const ll mod=1e9+7;
const int N=1e5+10;
int T;
ll n,m,v;
struct node{ll c,d;
}a[N];
bool cmp(node &A,node &B){return A.c<B.c;}//按照输入的下标排序
ll qsm(ll a,ll b){//快速幂，不知道为啥脑子抽抽打成了qsm，将错就错吧ll res=1ll;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
ll F(ll x){//计算F(x)函数ll ans=qsm(v,2*x)%mod;ans=(ans-qsm(v,x)+mod)%mod;//别忘了+modans=(ans+qsm(v,x-1))%mod;return ans%mod;
}
void solve(){ll ans=0ll;n=Read();m=Read();v=Read();for(int i=1;i<=m;i++){a[i].c=Read();a[i].d=Read();}sort(a+1,a+m+1,cmp);ans=qsm(v,2*(a[1].c-1));//开头for(int i=2;i<=m;i++){if(a[i].c==a[i-1].c){if(a[i].d!=a[i-1].d){//不合法puts("0");return ;}else continue;}ans=ans*F(a[i].c-a[i-1].c)%mod;}ans=ans*qsm(v,2*(n-a[m].c))%mod;//结尾printf("%lld\n",ans);return ;
}
signed main(){ T=Read();while(T--){solve();//多测函数好}return 0;
}