P11362 思路

模拟以下样例

CPP

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

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

如何填写

a

b

的值才能使符合条件的 $x_n$ 不存在呢？

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

模拟样例时发现

x_{1-n}

如下：

CPP

? , 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)

就得到了这一数段的正向可能数.

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

得到的并非结果

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

补充：

注意遍历时不要忘了上一个二元关系的尾是下一个二元关系的头
数据比较大，要用快速幂并开long long
$n$ 较大，无法开对应大小的 $x$ 数组，只需要存储 $c$ 的值就可以了

正解代码附上：

CPP

#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;
}

P11362 思路

文章操作

P11362 思路

相关推荐

评论

P11362 思路