提出 #46216646

ソースコード 拡げる

// LUOGU_RID: 127620709
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll Mod=1e9+7;

int a[55];
ll dp[1<<15];
ll pw[1<<15];
int tot[1<<15];
int n,m;

int main(){
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),x--,y--,a[x]|=(1<<y);
	pw[0]=1;for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2%Mod;
	for(int i=0;i<(1<<n);i++) for(int j=0;j<n;j++) tot[i]+=((i>>j)&1);
	dp[0]=1;
	for(int i=0;i<(1<<n);i++){
		for(int j=i;j;j=(j-1)&i) if(!((j&1)&&(j&2))){
			ll now=1;int S=i^j;
			for(int k=0;k<n;k++){
				if(S&(1<<k)) now*=(pw[tot[a[k]&j]]-1),now%=Mod;
				else if(j&(1<<k)) now*=pw[tot[a[k]&S]],now%=Mod;
			}
//			printf("%d %d %lld\n",i,j,now);
			dp[i]+=now*dp[S]%Mod,dp[i]%=Mod;
		}
	}
	cout<<dp[(1<<n)-1];
	return 0;
}

提出情報

提出日時
問題 F - Games on DAG
ユーザ cqbz_xiaofang
言語 C++ 17 (gcc 12.2)
得点 1600
コード長 747 Byte
結果 AC
実行時間 766 ms
メモリ 4288 KiB

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:15:40: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |         for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),x--,y--,a[x]|=(1<<y);
      |                                   ~~~~~^~~~~~~~~~~~~~

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 1600 / 1600
結果
AC × 4
AC × 40
セット名 テストケース
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt
ケース名 結果 実行時間 メモリ
0_00.txt AC 1 ms 3808 KiB
0_01.txt AC 1 ms 3732 KiB
0_02.txt AC 1 ms 3592 KiB
0_03.txt AC 1 ms 3556 KiB
1_00.txt AC 1 ms 3684 KiB
1_01.txt AC 762 ms 4044 KiB
1_02.txt AC 761 ms 4036 KiB
1_03.txt AC 763 ms 3988 KiB
1_04.txt AC 762 ms 3972 KiB
1_05.txt AC 766 ms 4036 KiB
1_06.txt AC 763 ms 4092 KiB
1_07.txt AC 761 ms 4052 KiB
1_08.txt AC 762 ms 4180 KiB
1_09.txt AC 764 ms 4028 KiB
1_10.txt AC 760 ms 4288 KiB
1_11.txt AC 760 ms 4184 KiB
1_12.txt AC 762 ms 3992 KiB
1_13.txt AC 761 ms 4272 KiB
1_14.txt AC 761 ms 4048 KiB
1_15.txt AC 761 ms 3928 KiB
1_16.txt AC 761 ms 4056 KiB
1_17.txt AC 763 ms 3988 KiB
1_18.txt AC 762 ms 4180 KiB
1_19.txt AC 761 ms 4048 KiB
1_20.txt AC 761 ms 4048 KiB
1_21.txt AC 4 ms 3748 KiB
1_22.txt AC 761 ms 4048 KiB
1_23.txt AC 761 ms 4032 KiB
1_24.txt AC 245 ms 3868 KiB
1_25.txt AC 2 ms 3704 KiB
1_26.txt AC 761 ms 3972 KiB
1_27.txt AC 26 ms 3772 KiB
1_28.txt AC 761 ms 4032 KiB
1_29.txt AC 80 ms 3996 KiB
1_30.txt AC 26 ms 3784 KiB
1_31.txt AC 763 ms 3972 KiB
1_32.txt AC 80 ms 3752 KiB
1_33.txt AC 26 ms 3852 KiB
1_34.txt AC 245 ms 4004 KiB
1_35.txt AC 80 ms 3836 KiB