WYX1210 @ 2024-12-01 15:39:30
本地能过大样例,跟题解对拍很多组也没有问题
#include<bits/stdc++.h>
#define int long long
#define maxn 200005
#define multicase() int t;cin>>t;while(t--)
using namespace std;
const int mod = 1e9 + 7;
int n,m,v;
map<int,int> a;
vector<int> b;
int ksm(int x,int y)
{
int res = 1;
while(y)
{
if(y&1) (res *= x) %= mod;
y>>= 1;
(x *= x) %= mod;
}
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
multicase()
{
a.clear();
b.clear();
cin >> n >> m >> v;
bool flag = 0;
for(int i=1;i<=m;i++){
int x,y;
cin >> x >> y;
if(a[x])
{
if(a[x] != y) flag = 1;
}
else a[x] = y,b.push_back(x);
}
if(flag)
{
cout << 0 << "\n";
continue;
}
sort(b.begin(),b.end());
bool noval = 1;
int lst = 1,ans = 1;
if(b.empty())
{
ans = ksm(v,2*n-2);
ans %= mod;
cout << ans << "\n";
continue;
}
ans = ksm(v,2*(b[0]-1)) * ksm(v,2*(n-b[b.size()-1]));
ans %= mod;
for(int i=1;i<b.size();i++)
{
// cout << "i = " << i << "\n";
ans *= ((ksm(v,2*(b[i]-b[i-1])) - ksm(v,(b[i]-b[i-1])) + ksm(v,(b[i]-b[i-1]-1))))%mod;
ans %= mod;
}
ans %= mod;
cout << ans << "\n";
}
return 0;
}
by 142857tree @ 2024-12-01 15:44:25
会不会有负数
by AllenJYL @ 2024-12-01 15:46:21
ans *= ((ksm(v,2*(b[i]-b[i-1])) - ksm(v,(b[i]-b[i-1])) + ksm(v,(b[i]-b[i-1]-1))))%mod;
这样写可能会乘一个负数进去,减法后面加一个 +mod
应该就可以了。
by WYX1210 @ 2024-12-01 15:50:21
感谢!@AllenJYL
by liuxy1234 @ 2024-12-01 16:05:53
破防了,过了大样例之后没再看了,我也没+mod
by liuxy1234 @ 2024-12-01 16:06:24
@liuxy1234
ccf样例不卡数据要是卡了就是**