P11362 思路

· · 个人记录

P11362 思路

模拟以下样例

10 11 2
10 2
7 2
7 2
2 2
3 2
4 2
10 2
7 2
10 2
3 2
3 2

模拟完，发现结果与d无关（然而并没有什么用）

正向考虑了很久，发现并不好做，考虑反向 然而最后还是回到正向了，不过反向用来过渡确实好思考很多.

如何填写a&b的值才能使符合条件的x_n不存在呢？

啰嗦两句，不难发现a_i b_i 只能使满足条件的x_i不存在

模拟样例时发现x_{1-n}如下：

? , 2 , 2 , 2 , ? , ? , 2 , ?  , ? , 2 .

不难发现无论a_1、b_1如何填写，都没办法使满足条件的x_{1-n} 因为没有满足条件的x_1而不存在

不难发现原因是这是一段无头的数段.
同样的，对于无尾的数段也会出现上述情况.

现在对中间有头有尾的数段进行考虑.
考虑a_2,b_2 发现只有在a_2=2 & b_2=1 时符合条件,尝试将其转化为含v的通式，如下:

a_2=x_2,b_2\neq x_2

共计v-1种可能. 同样的，a_3,b_3也符合上述通式.

考虑x_4-x_7数段
很难发现，只有

a_4=x_4，a_5=b_4，a_6=b_5，a_7=b_6，b_7\neq x_7

时符合条件，共计v*v*(v-1)种可能，因为a_4只有一种可能.
这里有点难理解，所以不难发现我使用了很难发现

很难发现，这些可能之间是或关系.
所以再次反向考虑，也就是用x_4-x_7的全排列可能数减去v*v*(v-1)
就得到了这一数段的正向可能数.

同理，将其他有头有尾数段的正向可能数壹壹求出后相乘

得到的并非结果

只需将无头与无尾数段的正向可能数相乘再乘上前面得到的结果即可.

补充：

正解代码附上：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=1e6+5;
const long long M=1e9+7;

ll T;
ll n,m,v;
ll sum;
ll flag=1;
ll l,r,p,ans=1;
pair<ll,ll> c[maxn];
int cnt;

ll quick_power(ll a,ll b){
    ll res=1;
    for(;b>0;){
        if(b%2==1){
            res*=a;
            res%=M;
            b--;
        }
        if(b%2==0){
            a*=a;
            a%=M;
            b>>=1;
        }
    }
    return res;
}

void init(){
    cin>>n>>m>>v;
    for(int i=1;i<=m;i++){
        cin>>c[i].first>>c[i].second;
    }
}

long long _pow(ll a,ll b){
    int t=a%M;
    if(b==0) return 1;
    for(int i=1;i<=b-1;i++){
        a*=t;
        a%=M;
    }
    return a%M;
}

void del(){
    sort(c+1,c+1+m);
    cnt++;
    for(int i=1;i<=m-1;i++){
        if(c[i].first==c[i+1].first){
            if(c[i].second!=c[i+1].second) flag=0;
        }
        else{
            c[++cnt].first=c[i+1].first;
            c[cnt].second=c[i+1].second;
        }
    }
}

int main(){
    cin>>T;
    while(T--){
        cnt=0;
        l=0;
        r=0;
        sum=0;
        ans=1;
        flag=1;
        memset(c,0,sizeof(c));
        init();
        del();
        if(flag){
            for(int i=1;i<=cnt;i++){
                if(l==0) l=c[i].first;
                else if(r==0) r=c[i].first;
                if(l!=0 && r!=0){
                    p=r-l;
                    sum+=p;
                    ll t=(quick_power(v,2*p)%M-quick_power(v,p-1)*(v-1)%M);
                    if(t<0) ans*=(t+M);
                    else ans*=t;
                    ans%=M;
                    l=r;
                    r=0;
                }
            }
            ans*=quick_power(v,2*(n-1-sum));
            ans%=M;
            cout<<ans<<endl;
        }
        else cout<<0<<endl;
    }
    return 0;
}