P11362 [NOIP2024] 遗失的赋值 题解

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(x)=v \times f(x-1) + v^{2x}-v^{2x-1} \]

边界为 \(F(1)=v^2-v+1\)，即二元限制的第一个数与左边的数不同的 \(v(v−1)\) 种情况，加上这两个数相同则右边的两个数也必须相同的 \(1\) 种情况。

将 \(F(x-1)\) 用 \(F(x-2)\) 代入得

\[F(x)=v^{2x}-v^{2x-1}+v \times (v^{2x-2}-v^{2x-3}+v \times F(x-2)) \\ F(x)=v^{2x}-v^{2x-1}+v^{2x-1}-v^{2x-2}+v^2 \times F(x-2) \\ F(x)=v^{2x}-v^{2x-2}+v^2 \times F(x-2) \]

将 \(F(x-2)\) 用 \(F(x-3)\) 代入得

\[F(x)=v^{2x}-v^{2x-2}+v^2 \times (v^{2x-4}-v^{2x-5}+v \times F(x-3)) \\ F(x)=v^{2x}-v^{2x-2}+v^{2x-2}-v^{2x-3}+v^3 \times F(x-3) \\ F(x)=v^{2x}-v^{2x-3}+v^3 \times F(x-3) \]

于是我们得到了

\[F(x)=v^{2x}-v^{2x-k}+v^k \times F(x-k) \]

代入 \(k=x-1\) 得到

\[F(x)=v^{2x}-v^{2x-x+1}+v^{x-1} \times F(1) \\ F(x)=v^{2x}-v^{x+1}+v^{x-1} \times (v^2-v+1) \\ F(x)=v^{2x}-v^{x+1}+v^{x+1}-v^x+v^{x-1} \\ F(x)=v^{2x}- v^x+v^{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;
}