第一题：破碎的矩阵

题目链接：https://ac.nowcoder.com/acm/contest/932/A

　　　刚看到这题的时候感觉特别熟悉...诶，这不就是codeforces某场比赛的某某题吗？（心里激动了一波）仔细看完题目

　　　才发现这并不是codeforces那道构造题，但是多多少少还是有点类似...那题是问我们矩阵是否可以构造，这题则问的

　　　是最多可以构造几个符合题意的矩阵。

　　首先要做的和cf那题一样都是先将每行的异或和异或后存于ans1，每列的异或和异或后存于ans2，这样ans1就等于每

　　一行的每个元素异或总和，ans2就等于每一列的每个元素异或总和。

　　　很快我们会发现ans1、ans2其实就是这个矩阵的每一个元素的异或和，那么当ans1^ans2==0（即ans1 == ans2）时，　　

　　　用题目数据构造出来的矩阵就是合法的了，否则该矩阵不存在，直接输出0即可。

　　　那么当矩阵合法的时候我们怎么算出符合题意的矩阵的个数呢？

　　其实很简单——对于每行，我们可以在前面n-1列任意放置一个小于等于x的数，而第n列总有唯一合法的填数方案。

　　　同理对于每一列也是一样的，所以我们可以得出合法的矩阵的总个数就是（x+1）的（n-1）*（m-1）次方

　　　下面贴代码

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define inf 0x3f3f3f

 const ll  N = 1e6+;

 ll pow_mod(ll a, ll n, ll m)

 {

     a%=m;

     long long ans = ;

     while(n)

     {

         if(n&)

         {

             ans = (ans * a) % m;

         }

         a = (a * a) % m;

         n >>= ;

     }

     return ans;

 }

 ll n,m,x,p;

 ll a[N],b[N];

 int  main()

 {

     ios::sync_with_stdio(false);

     int t;

     cin>>t;

     while(t--)

     {

         cin>>n>>m>>x>>p;

         ll ans1,ans2;

         for(ll i=; i<=n; i++)

         {

             cin>>a[i];

             if(i == )

                 ans1 = a[i];

             else

                 ans1 = ans1^a[i];

         }

         for(ll i=; i<=m; i++)

         {

             cin>>b[i];

             if(i == )

                 ans2 = b[i];

             else

                 ans2 = ans2^b[i];

         }

         if(ans1^ans2)

         {

             cout<<<<endl;

             continue;

         }

         ll ans = pow_mod(x+,(n-)*(m-),p);

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

牛客NOIP暑期七天营-提高组3

第一题：破碎的矩阵

题目链接：https://ac.nowcoder.com/acm/contest/932/A

第二题bit树调bug调了三十分钟测试样例还是没过，所以果断暴力取30分。

暴力完第二题已经快11点了，此时心态已崩。想着11点就可以和小伙伴们去

吃饭，直接写个特判拿了5分

以后题解多了会把这两题也补上，目前就这样...

最新文章

热门文章