제출 #345673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
345673		oleh1421	Intergalactic ship (IZhO19_xorsum)	C++17	100 / 100	741 ms	203576 KiB

xorsum

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define endl '\n'
const int N=1010;
const ll mod=1000000007;
int S[7][7][N][N];
int a[N];
ll pw[N*N];
void solve(){
    pw[0]=1ll;
    for (int i=1;i<N*N;i++){
        pw[i]=(pw[i-1]*2ll)%mod;
    }
    int n;cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    int q;cin>>q;
    for (int i=1;i<=q;i++){
        int l,r,x;cin>>l>>r>>x;
        for (int j=0;j<7;j++){
            for (int t=0;t<7;t++){
                if ((x&(1<<j)) && (x&(1<<t))){
                    S[j][t][l][r]++;
                }
            }
        }
    }
    for (int x=0;x<7;x++){
        for (int y=0;y<7;y++){
            for (int i=1;i<=n;++i){
                for (int j=1;j<=n;j++) S[x][y][i][j]+=S[x][y][i][j-1];
                for (int j=1;j<=n;j++) S[x][y][i][j]+=S[x][y][i-1][j];
            }
        }
    }
    ll res=0ll;
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++){
            ll mult=i*(n-j+1);
            if (i<j) mult*=2;
            for (int x=0;x<7;x++){
                for (int y=0;y<7;y++){
//                    1<=l<=i
//                    i<=r<=n
                    int cnt=S[x][y][i][n]-S[x][y][0][j]-S[x][y][i][j-1]+S[x][y][0][j-1];
                    int cnt_x=S[x][x][i][n]-S[x][x][0][i-1]-S[x][x][i][i-1]+S[x][x][0][i-1];
                    int cnt_y=S[y][y][j][n]-S[y][y][0][j-1]-S[y][y][j][j-1]+S[y][y][0][j-1];
                    cnt_x-=cnt;
                    cnt_y-=cnt;
                    int SS=(cnt>0)+(cnt_x>0)+(cnt_y>0);
//                    if (i==1 && j==1 && x==0 && y==1){
//                        cout<<"OK "<<mult<<" "<<SS<<endl;
//                    }
//                    if (i==1 && j==1 && x==0 && y==1){
//                        cout<<"OK "<<mult<<" "<<SS<<endl;
//                    }
//                    if (i==1 && j==1 && x==0 && y==1){
//                        cout<<"OK "<<mult<<" "<<SS<<endl;
//                    }
//                    if (i==1 && j==1 && x==0 && y==1){
//                        cout<<"OK "<<mult<<" "<<SS<<endl;
//                    }
                    if (SS>=2){
                        res+=pw[q-2+x+y]*mult;
                        res%=mod;
                    } else if ((a[i]&(1<<x)) && (a[j]&(1<<y))){
//                        cout<<i<<" "<<j<<" "<<x<<" "<<y<<endl;
//                        cout<<mult<<endl;
                        res+=pw[q-SS+x+y]*mult;
                        res%=mod;
                    } else if ((a[i]&(1<<x)) && (a[j]&(1<<y))==0 && cnt_y){
                        res+=pw[q-SS+x+y]*mult;
                        res%=mod;
                    } else if ((a[i]&(1<<x))==0 && (a[j]&(1<<y)) && cnt_x){
                        res+=pw[q-SS+x+y]*mult;
                        res%=mod;
                    } else if ((a[i]&(1<<x))==0 && (a[j]&(1<<y))==0 && cnt){
                        res+=pw[q-SS+x+y]*mult;
                        res%=mod;
                    }
                }
            }
        }
    }
    cout<<res<<endl;
}
int32_t main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
    while (tt--){
        solve();
    }

    return 0;
}
/*
2
1 3
1
1 2 2

*/

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 11 / 11
• Subtask 7: 19 / 19
• Subtask 8: 30 / 30
• Subtask 9: 8 / 8