求助，暴力思路为什么不对

thousands_of_years @ 2024-12-01 17:56:45

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int a[10000000];
 main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m,v;
        cin>>n>>m>>v;
        bool io=0;
        for(int i=1;i<=m;i++)
        {
            int l,r;
            cin>>l>>r;
            if(a[l]!=r && a[l]!=0)
            io=1;
            a[l]=r;
        }
        int ans=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i] && a[i-1])
            ans=(ans*((v-1)*v%mod+1))%mod;
            else
            ans=ans*v%mod*v%mod;
        }
        if(!io)
        cout<<ans<<endl;
        else
        cout<<0<<endl;
        for(int i=1;i<=n;i++)
        a[i]=0; 
    }
    return 0;
}

by ssfx2019s005 @ 2024-12-01 18:01:55

同问，我考场上也是这样想的

by SJS_z @ 2024-12-01 18:17:12

我记得大样例有一个<10的点能hack吧

by PvbeLLN @ 2024-12-01 18:21:44

同，样例有个 n=12 的点过不去。

by r2bxyy @ 2024-12-01 18:37:58

考虑一段被两个有值的数字框出来的段[l,r]，这里我们只考虑[l,r-1]，r留给下一段，那么对于这一整段来说只有当全部都接上且r-1位不是r的数值的时候才会非法。因为他问是有多少种取值可以构造出合法状态。\ 以下是我的考场思路，对是对了，但是好像不是最简单的办法：\ 对于这一段中的每个点去枚举从这一位开始破除首尾相连的状态，那么在这之前状态数每一位是v（a与上一位相同，b随便选），当前位是（v（v-1）），后面都是v^2。最后还有一种特殊情况就是全部首尾相连但是r-1处的b数组符合r的值，l到r-2为v，r-1为1种情况，最后乘起来就会得到：\ 令r-l=g，则有： 当前答案=l处的答案乘上(v^{2g-1}+v^{2g-2}+...+v^{g})(v-1)+v^{g-1} 用等比数列处理一下就好了，最后结果是：v^{2g}-v^g+v^{g-1}\ 注意初始化和前面和最后一段没有定值的话全部乘上v^2就好了

by r2bxyy @ 2024-12-01 18:38:44

@thousands_of_years

by XuYueming @ 2024-12-01 19:16:49

同问，我考场上也是这样想的

by ssfx2019s005 @ 2024-12-01 20:38:15

@SJS_z 是的

by thousands_of_years @ 2024-12-02 14:35:46

@r2bxyy thx